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 NPcomplete. 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 P 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 timebounded 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 worstcase 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.