ECCC-Report TR21-089https://eccc.weizmann.ac.il/report/2021/089Comments and Revisions published for TR21-089en-usFri, 25 Jun 2021 18:28:02 +0300
Paper TR21-089
| A Relativization Perspective on Meta-Complexity |
Rahul Santhanam,
Hanlin Ren
https://eccc.weizmann.ac.il/report/2021/089Meta-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:
* 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.
* 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.
* Levin's time-bounded Kolmogorov complexity Kt(x) can be approximated to a factor (2+epsilon) in polynomial time, for any epsilon > 0.
* 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.
* 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].Fri, 25 Jun 2021 18:28:02 +0300https://eccc.weizmann.ac.il/report/2021/089