Gap MCSP is not (Levin) NP-complete in Obfustopia

ePrint Report: Gap MCSP is not (Levin) NP-complete in Obfustopia

Noam Mazor, Rafael Pass

We demonstrate that under believable cryptographic hardness assumptions, Gap versions of standard meta-complexity problems, such as the Minimum Circuit Size problem (MCSP) and the Minimum Time-Bounded Kolmogorov Complexity problem (MKTP) are not NP-complete w.r.t. Levin (i.e., witness-preserving many-to-one) reductions.


In more detail:
- Assuming the existence of indistinguishability obfuscation, and subexponentially-secure one-way functions, an appropriate Gap version of MCSP is not NP-complete under randomized Levin-reductions.
- …

complexity cryptographic eprint report gap meta pass problem problems report size standard under