Ren, Hanlin ;
Santhanam, Rahul
A Relativization Perspective on MetaComplexity
Abstract
Metacomplexity 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 metacomplexity. 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 searchtodecision reduction for MCSP with a relativizing proof.
2) The complexities of MCSP[2^{n/2}] and MCSP[2^{n/4}] are different, in both worstcase and averagecase settings. Thus the complexity of MCSP is not "robust" to the choice of the size function.
3) Levin’s timebounded 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 auxiliaryinput oneway functions. In contrast, Santhanam [ITCS'20] gave a relativizing proof that the nonexistence of natural proofs implies the existence of oneway 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].
BibTeX  Entry
@InProceedings{ren_et_al:LIPIcs.STACS.2022.54,
author = {Ren, Hanlin and Santhanam, Rahul},
title = {{A Relativization Perspective on MetaComplexity}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {54:154:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15864},
URN = {urn:nbn:de:0030drops158646},
doi = {10.4230/LIPIcs.STACS.2022.54},
annote = {Keywords: metacomplexity, relativization, minimum circuit size problem}
}
09.03.2022
Keywords: 

metacomplexity, relativization, minimum circuit size problem 
Seminar: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Issue date: 

2022 
Date of publication: 

09.03.2022 