Chen, Lijie ;
McKay, Dylan M. ;
Murray, Cody D. ;
Williams, R. Ryan
Relations and Equivalences Between Circuit Lower Bounds and KarpLipton Theorems
Abstract
A frontier open problem in circuit complexity is to prove P^{NP} is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P_{/poly}. Previously, for several classes containing P^{NP}, including NP^{NP}, ZPP^{NP}, and S_2 P, such lower bounds have been proved via KarpLiptonstyle Theorems: to prove C is not in SIZE[n^k] for all k, we show that C subset P_{/poly} implies a "collapse" D = C for some larger class D, where we already know D is not in SIZE[n^k] for all k.
It seems obvious that one could take a different approach to prove circuit lower bounds for P^{NP} that does not require proving any KarpLiptonstyle theorems along the way. We show this intuition is wrong: (weak) KarpLiptonstyle theorems for P^{NP} are equivalent to fixedpolynomial size circuit lower bounds for P^{NP}. That is, P^{NP} is not in SIZE[n^k] for all k if and only if (NP subset P_{/poly} implies PH subset i.o. P^{NP}_{/n}).
Next, we present new consequences of the assumption NP subset P_{/poly}, towards proving similar results for NP circuit lower bounds. We show that under the assumption, fixedpolynomial circuit lower bounds for NP, nondeterministic polynomialtime derandomizations, and various fixedpolynomial time simulations of NP are all equivalent. Applying this equivalence, we show that circuit lower bounds for NP imply better KarpLipton collapses. That is, if NP is not in SIZE[n^k] for all k, then for all C in {ParityP, PP, PSPACE, EXP}, C subset P_{/poly} implies C subset i.o.NP_{/n^epsilon} for all epsilon > 0. Note that unconditionally, the collapses are only to MA and not NP.
We also explore consequences of circuit lower bounds for a sparse language in NP. Among other results, we show if a polynomiallysparse NP language does not have n^{1+epsilon}size circuits, then MA subset i.o.NP_{/O(log n)}, MA subset i.o.P^{NP[O(log n)]}, and NEXP is not in SIZE[2^{o(m)}]. Finally, we observe connections between these results and the "hardness magnification" phenomena described in recent works.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2019:10852,
author = {Lijie Chen and Dylan M. McKay and Cody D. Murray and R. Ryan Williams},
title = {{Relations and Equivalences Between Circuit Lower Bounds and KarpLipton Theorems}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {30:130:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10852},
URN = {urn:nbn:de:0030drops108525},
doi = {10.4230/LIPIcs.CCC.2019.30},
annote = {Keywords: KarpLipton Theorems, Circuit Lower Bounds, Derandomization, Hardness Magnification}
}
2019
Keywords: 

KarpLipton Theorems, Circuit Lower Bounds, Derandomization, Hardness Magnification 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 