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

It is a long-standing open problem whether the Minimum Circuit Size Problem (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 metacomplexity 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.

1. Assuming subexponentially-secure witness encryption exists, we prove essentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity (K 𝑡 (𝑥 | 𝑦)) in the regime where 𝑡 ≫ |𝑦|. Previously, the best hardness of approximation known was a |𝑥 | 1/poly(log log |𝑥 |) factor and only in the sublinear regime (𝑡 ≪ |𝑦|).

2. Unconditionally, we show that for any constant 𝑐 > 1, the Minimum Oracle Circuit Size Problem (MOCSP) is NP-hard to approximate, where Yes instances have circuit complexity at most 𝑠, and No instances have circuit complexity at least 𝑠 𝑐 . 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 𝑠 versus 10𝑠 log 𝑁 .

3. Finally, we define a "multi-valued" version of MCSP, called mvMCSP, and show that w.p. 1 over a random oracle 𝑂, it is NPhard to approximate mvMCSP 𝑂 under quasi-polynomial-time reductions with an 𝑂 oracle. 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.