2026-07-23T17:38:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15864 2024-03-06T10:56:23Z ddc:004 open_access

A Relativization Perspective on Meta-Complexity Ren, Hanlin Santhanam, Rahul meta-complexity relativization minimum circuit size problem Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where: 1) MCSP can be solved in deterministic polynomial time, but the search version of MCSP cannot be solved in deterministic polynomial time, even approximately. In contrast, Carmosino, Impagliazzo, Kabanets, Kolokolova [CCC'16] gave a randomized approximate search-to-decision reduction for MCSP with a relativizing proof. 2) The complexities of MCSP[2^{n/2}] and MCSP[2^{n/4}] are different, in both worst-case and average-case settings. Thus the complexity of MCSP is not "robust" to the choice of the size function. 3) Levin’s time-bounded Kolmogorov complexity Kt(x) can be approximated to a factor (2+ε) in polynomial time, for any ε > 0. 4) Natural proofs do not exist, and neither do auxiliary-input one-way functions. In contrast, Santhanam [ITCS'20] gave a relativizing proof that the non-existence of natural proofs implies the existence of one-way functions under a conjecture about optimal hitting sets. 5) DistNP does not reduce to GapMINKT by a family of "robust" reductions. This presents a technical barrier for solving a question of Hirahara [FOCS'20]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hanlin Ren and Rahul Santhanam 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.54 urn:nbn:de:0030-drops-158646 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.54 eng https://creativecommons.org/licenses/by/4.0/legalcode