Conference item
A relativization perspective on meta-complexity
- Abstract:
-
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].
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 828.9KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.STACS.2022.54
Authors
- Publisher:
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- Host title:
- 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
- Pages:
- 54:1-54:13
- Series:
- LIPIcs
- Series number:
- 219
- Place of publication:
- Dagstuhl, Germany
- Publication date:
- 2022-03-09
- Acceptance date:
- 2021-12-16
- Event title:
- 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
- Event location:
- Virtual event
- Event website:
- https://stacs2022.sciencesconf.org/
- Event start date:
- 2022-03-15
- Event end date:
- 2022-03-18
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959772228
- Language:
-
English
- Keywords:
- Pubs id:
-
1237075
- Local pid:
-
pubs:1237075
- Deposit date:
-
2022-01-31
Terms of use
- Copyright holder:
- Ren and Santhanam
- Copyright date:
- 2022
- Rights statement:
- © Hanlin Ren and Rahul Santhanam; licensed under Creative Commons License CC-BY 4.0.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record