2026-07-21T12:28:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10852 2024-03-06T10:46:52Z ddc:004 open_access

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems Chen, Lijie McKay, Dylan M. Murray, Cody D. Williams, R. Ryan Karp-Lipton Theorems Circuit Lower Bounds Derandomization Hardness Magnification 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 Karp-Lipton-style 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 Karp-Lipton-style theorems along the way. We show this intuition is wrong: (weak) Karp-Lipton-style theorems for P^{NP} are equivalent to fixed-polynomial 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, fixed-polynomial circuit lower bounds for NP, nondeterministic polynomial-time derandomizations, and various fixed-polynomial time simulations of NP are all equivalent. Applying this equivalence, we show that circuit lower bounds for NP imply better Karp-Lipton collapses. That is, if NP is not in SIZE[n^k] for all k, then for all C in {Parity-P, 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 polynomially-sparse 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lijie Chen and Dylan M. McKay and Cody D. Murray and R. Ryan Williams 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.30 urn:nbn:de:0030-drops-108525 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.30 eng https://creativecommons.org/licenses/by/3.0/legalcode