2026-07-25T23:33:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20432 2024-07-15T12:26:46Z ddc:004 open_access

Gap MCSP Is Not (Levin) NP-Complete in Obfustopia Mazor, Noam Pass, Rafael Kolmogorov complexity MCSP Levin Reduction 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. - 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noam Mazor and Rafael Pass 2024 Is Part Of LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2024.36 urn:nbn:de:0030-drops-204322 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.36 eng https://creativecommons.org/licenses/by/4.0/legalcode