Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

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 Ppoly 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 not subset SIZE[n^k] for all k if and only if (NP is in P/poly implies PH is in i.o.-P^NP/n).

Next, we present new consequences of the assumption NP is in 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 { ParP, PP, PSPACE, EXP }, C is in P/poly implies C is in i.o.-NP/n^eps for all eps > 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+eps)-size circuits, then MA is in i.o.-NP/O(log n), MA is in 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.