Hardness Magnification for all Sparse NP Languages
Lijie Chen, Ce Jin, Ryan Williams · 2019
In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of computing time-bounded Kolmogorov complexity. In [Oliveira and Santhanam, FOCS 2018], [Oliveira, Pich, and Santhanam, CCC 2019], and [McKay, Murray, and Williams, STOC 2019], it was shown that minor (n1+ε-style) lower bounds for MCSP[2o(m)] or MKtP[2o(m)] would imply breakthrough circuit lower bounds such as NP⊄P/poly, NP⊄NC1, or EXP⊄P/poly. We consider the question: What is so special about MCSP and MKtP? Why do they admit this striking phenomenon? One simple property is that all variants of MCSP (and MKtP) considered in prior work are sparse languages. For example, MCSP[s(m)] has 2Õ(s(m))yes-instances of length n = 2m, so MCSP[2o(m)] is 2no(1)-sparse. We show that there is a hardness magnification phenomenon for all equally-sparse NP languages. Formally, suppose there is an ε > 0 and a language L ∈ NP which is 2no(1)-sparse, and L ∈/ Circuit[n1+ε]. Then NP does not have nk-size circuits for all k. We prove analogous theorems for De Morgan formulas, B2-formulas, branching programs, AC0[6] and TC0circuits, and more: improving the state of the art in NP lower bounds against any of these models by an ε factor in the exponent would already imply NP lower bounds for all fixed polynomials. In fact, in our proofs it is not necessary to prove a (say) n1+εcircuit size lower bound for L: one only has to prove a lower bound against n1+ε-time nε-space deterministic algorithms with nεadvice bits. Such lower bounds are well-known for non-sparse problems. Building on our techniques, we also show interesting new hardness magnifications for search-MCSP and search-MKtP (where one must output small circuits or short representations of strings), showing consequences such as ⊕P (or PP, PSPACE, and EXP) is not contained in P/poly (or NC1, AC0[6], or branching programs of polynomial size). For instance, if there is an ε > 0 such that search-MCSP[2βm] does not have De Morgan formulas of size n3+εfor all constants ß > 0, then ⊕P⊄NC1.