SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle

The Minimum Circuit Size Problem (MCSP) is the task of deciding, given the truth table of a Boolean function f and a size parameter s, whether there is a circuit computing f of size at most s. It has been an open question since Levin’s seminal work on NP-completeness (1973) whether MCSP is NP-complete. This question has drawn further interest in light of recent connections between MCSP, learning theory, average-case complexity, and cryptography. We show that, with probability one, there is a black-box P / poly (as well as a PO^O) many-one reduction from (unrelativized) SAT to MCSP on circuits with access to a random oracle O. This resolves an open question of Huang, Ilango, and Ren (STOC 2023) who conjectured the existence of such a reduction. Two important ingredients in our proof are 1) a relaxation of symmetry of information that we call pseudo symmetry of information and 2) a subroutine of the reduction that essentially is a cryptographic proof of work. Our reduction yields additive hardness of approximation that is optimal up to a constant factor and extends to a variety of other metacomplexity problems, including computing time-bounded Kolmogorov complexity (K^t). Applying the random oracle heuristic from cryptography, where one heuristically “instantiates” O with a real-world cryptographic hash function, we get a plethora of candidate deterministic polynomial-time many-one reductions from SAT to MCSP and K^t in the standard unrelativized world. To our knowledge, no candidate reduction from SAT to MCSP or K^t was known previously. Moreover, the hardness of approximation in these candidate reductions would imply the NP-hardness of the gap version of K^t that Hirahara (FOCS 2018) shows has a non-black-box worst-case to average-case reduction. Intriguingly, as a consequence we get that the existence of sufficiently “unstructured” functions implies that a problem with a known (non-black-box) worst-case to average-case reduction is NP-complete.