A relativization perspective on meta-complexity
<p>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:<...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2022
|
| _version_ | 1826307442554699776 |
|---|---|
| author | Ren, H Santhanam, R |
| author_facet | Ren, H Santhanam, R |
| author_sort | Ren, H |
| collection | OXFORD |
| description | <p>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:</p>
<p>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.</p>
<p>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.</p>
<p>3) Levin’s time-bounded Kolmogorov complexity Kt(x) can be approximated to a factor (2+ε) in polynomial time, for any ε > 0.</p>
<p>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.</p>
<p>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].</p> |
| first_indexed | 2024-03-07T07:03:12Z |
| format | Conference item |
| id | oxford-uuid:6963f99a-4cba-4a15-a958-2d55133b0e82 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:03:12Z |
| publishDate | 2022 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:6963f99a-4cba-4a15-a958-2d55133b0e822022-04-01T12:15:42ZA relativization perspective on meta-complexityConference itemhttp://purl.org/coar/resource_type/c_5794uuid:6963f99a-4cba-4a15-a958-2d55133b0e82EnglishSymplectic ElementsSchloss Dagstuhl - Leibniz-Zentrum für Informatik2022Ren, HSanthanam, R<p>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:</p> <p>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.</p> <p>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.</p> <p>3) Levin’s time-bounded Kolmogorov complexity Kt(x) can be approximated to a factor (2+ε) in polynomial time, for any ε > 0.</p> <p>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.</p> <p>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].</p> |
| spellingShingle | Ren, H Santhanam, R A relativization perspective on meta-complexity |
| title | A relativization perspective on meta-complexity |
| title_full | A relativization perspective on meta-complexity |
| title_fullStr | A relativization perspective on meta-complexity |
| title_full_unstemmed | A relativization perspective on meta-complexity |
| title_short | A relativization perspective on meta-complexity |
| title_sort | relativization perspective on meta complexity |
| work_keys_str_mv | AT renh arelativizationperspectiveonmetacomplexity AT santhanamr arelativizationperspectiveonmetacomplexity AT renh relativizationperspectiveonmetacomplexity AT santhanamr relativizationperspectiveonmetacomplexity |