Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-165 | 5th November 2023 07:05

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


Authors: Rahul Ilango
Publication: 6th November 2023 05:00
Downloads: 914


The Minimum Circuit Size Problem (MCSP) asks, given the truth table of a Boolean function $f$ and an integer $s$, if 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 whether MCSP is NP-complete. This question has drawn further interest in light of connections between MCSP and other areas, such as learning theory, average-case complexity, cryptography, and proof complexity. These connections arise from seemingly special properties of MCSP that are not currently known for any NP-complete problem.

We give, in our view, the strongest evidence yet that MCSP is in fact NP-complete. Specifically, we show that, with probability one, there is a P/poly reduction from the NP-hard problem of approximating vertex cover on hypergraphs to MCSP on circuits that have access to a uniformly random oracle $O$ (the reduction can be made uniform if it is given access to $O$). This resolves an open question of Huang, Ilango, and Ren (STOC 2023), who conjectured such a reduction exists. Curiously, a key part of our reduction is computing a cryptographic proof of work.

Our reduction yields near-optimal additive hardness of approximation and extends to computing time-bounded Kolmogorov complexity ($K^t$). Heuristically "instantiating" $O$ with real-world cryptographic hash functions, we get a plethora of candidate uniform 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, our results hold in the regime where $K^t$ has a non-black-box worst-case to average-case reduction (Hirahara, FOCS 2018). Thus, intriguingly, the existence of sufficiently "unstructured" functions implies a problem with a known (non-black-box) worst-case to average-case reduction is NP-complete.

ISSN 1433-8092 | Imprint