Abstract

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 talk, we discuss 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. Using this approach, we show:
- Assuming subexponentially-secure indistinguishability obfuscation exists, we prove es-
sentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov
complexity (Kt(x | y)) in the regime where t ≫ |y|.

• Unconditionally, for any constant c > 1, the Minimum Oracle Circuit
Size Problem (MOCSP) is NP-hard to approximate, where Yes instances have circuit
complexity at most s, and No instances have circuit complexity at least s^c.

Video Recording