ECCC-Report TR24-053https://eccc.weizmann.ac.il/report/2024/053Comments and Revisions published for TR24-053en-usMon, 18 Mar 2024 10:28:32 +0200
Paper TR24-053
| Gap MCSP is not (Levin) NP-complete in Obfustopia |
Noam Mazor,
Rafael Pass
https://eccc.weizmann.ac.il/report/2024/053We 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.
- Assuming the existence of subexponentially-secure indistinguishability obfuscation, subexponentially-secure one-way functions and injective PRGs, an appropriate Gap version of MKTP is not NP-complete under randomized Levin-reductions.Mon, 18 Mar 2024 10:28:32 +0200https://eccc.weizmann.ac.il/report/2024/053