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

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

Yizhi Huang, Rahul Ilango, Hanlin Ren

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 …

cases complexity construction correctness eprint report key meta problem problems prove report security size work