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.