Expanding the Reach of P not equal to NP: the Minimum Circuit Size Problem with a Random Oracle is NP-hard

In this talk, I will discuss progress on showing hardness of the Minimum Circuit Size Problem (MCSP). The computational complexity of MCSP is a longstanding mystery, dating back as far as Levin's seminal work on NP-completeness in 1973. Over the past several years, researchers have utilized MCSP's seemingly special properties (properties not known for, say, SAT) to prove intriguing connections between MCSP and other areas of theoretical computer science, including learning theory, cryptography, average-case complexity, and proof complexity.

We give, in our view, the strongest evidence yet that MCSP is in fact NP-complete (and thus that SAT does indeed have these special properties) by giving a reduction in the presence of a "random oracle." In particular our results yield the first candidate reduction from SAT to MCSP and show that the existence of sufficiently "unstructured" functions implies a problem with a known (non-black-box) worst-case to average-case reduction is NP-complete. Curiously, a key part of our reduction involves computing a cryptographic proof of work.

No background knowledge on MCSP or other areas of complexity is required!