Hardness magnification near state-of-the-art lower bounds

Journal article

This article continues the development of hardness magnification, an emerging area that proposes a new strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.
We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs to distinguish instances (strings or truth-tables) of complexity ≤s1(N) from instances of complexity ≥s2(N), and N=2n denotes the input length. In MCSP, complexity is measured by circuit size, while in MKtP one considers Levin's notion of time-bounded Kolmogorov complexity. (In our results, the parameters s1(N) and s2(N) are asymptotically quite close, and the problems almost coincide with their standard formulations without a gap.) We establish that for Gap−MKtP[s1,s2] and Gap−MCSP[s1,s2], a marginal improvement over the state of the art in unconditional lower bounds in a variety of computational models would imply explicit superpolynomial lower bounds, including P≠NP.
Theorem. There exists a universal constant c≥1 for which the following hold. If there exists ε>0 such that for every small enough β>0
[(1)] Gap−MCSP[2βn/cn,2βn]∉Circuit[N1+ε], then NP⊈Circuit[poly].
[(2)] Gap−MKtP[2βn,2βn+cn]∉B2-Formula[N2+ε], then EXP⊈Formula[poly].
[(3)] Gap−MKtP[2βn,2βn+cn]∉U2-Formula[N3+ε], then EXP⊈Formula[poly].
[(4)] Gap−MKtP[2βn,2βn+cn]∉BP[N2+ε], then EXP⊈BP[poly].
These results are complemented by lower bounds for Gap−MCSP and Gap−MKtP against different models. For instance, the lower bound assumed in (1) holds for U2-formulas of near-quadratic size, and lower bounds similar to (2)-(4) hold for various regimes of parameters.
We also identify a natural computational model under which the hardness magnification threshold for Gap−MKtP lies below existing lower bounds: U2-formulas that can compute parity functions at the leaves (instead of just literals). As a consequence, if one managed to adapt the existing lower bound techniques against such formulas to work with Gap−MKtP, then EXP⊈NC1 would follow via hardness magnification.

Authors: Oliveira, IC; Pich, J; Santhanam, R

• Publication status: Published
• Peer review status: Peer reviewed
• Journal: Theory of Computing
• Volume: 17
• Issue: CCC 2019 Special Issue
• Pages: 1-38
• Article number: 11
• Publication date: 2021-11-20
• Acceptance date: 2021-02-27
• DOI: 10.4086/toc.2021.v017a011
• ISSN: 1557-2862
• Language: English
• Keywords: lower bounds; minimum circuit size; circuit complexity; complexity theory; Kolmogorov complexity; FFR