NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
Yizhi Huang, Rahul Ilango, Hanlin Ren · 2023
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.