Paper 2023/528

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

Yizhi Huang, Tsinghua University
Rahul Ilango, Massachusetts Institute of Technology
Hanlin Ren, University of Oxford

It is a long-standing open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation. In this work, we prove NP-hardness of approximating meta-complexity with nearly-optimal approximation gaps. Our key idea is to use *cryptographic constructions* in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. We present both conditional and unconditional hardness of approximation results as follows. $\bullet$ Assuming subexponentially-secure witness encryption exists, we prove essentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity ($\mathrm{K}^t(x \mid y)$) in the regime where $t \gg |y|$. Previously, the best hardness of approximation known was a $|x|^{1/ \mathrm{poly}(\log \log |x|)}$ factor and only in the sublinear regime ($t \ll |y|$). $\bullet$ Unconditionally, we show near-optimal NP-hardness of approximation for the Minimum Oracle Circuit Size Problem (MOCSP), where Yes instances have circuit complexity at most $2^{\varepsilon n}$, and No instances are essentially as hard as random truth tables. Our reduction builds on a witness encryption construction proposed by Garg, Gentry, Sahai, and Waters (STOC'13). Previously, it was unknown whether it is NP-hard to distinguish between oracle circuit complexity $s$ versus $10s\log N$. $\bullet$ Finally, we define a "multi-valued" version of $\mathrm{MCSP}$, called $\mathrm{mvMCSP}$, and show that w.p. $1$ over a random oracle $O$, $\mathrm{mvMCSP}^O$ is NP-hard to approximate under quasi-polynomial-time reductions with $O$ oracle access. Intriguingly, this result follows almost directly from the security of Micali's CS proofs (Micali, SICOMP'00). In conclusion, we give three results convincingly demonstrating the power of cryptographic techniques in proving NP-hardness of approximating meta-complexity.

Available format(s)
Publication info
Published elsewhere. STOC 2023
witness encryptionSNARGCS proofsminimum circuit size problemKolmogorov complexityhardness of approximation
Contact author(s)
huangyizhi01 @ gmail com
rilango @ mit edu
h4n1in r3n @ gmail com
2023-04-12: approved
2023-04-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yizhi Huang and Rahul Ilango and Hanlin Ren},
      title = {NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach},
      howpublished = {Cryptology ePrint Archive, Paper 2023/528},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.