Revised: February 27, 2021
Published: November 30, 2021
Abstract: [Plain Text Version]
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 $\mathsf{MKtP}$ and $\mathsf{MCSP}$, where one needs to distinguish instances (strings or truth-tables) of complexity $\leq s_1(N)$ from instances of complexity $\geq s_2(N)$, and $N = 2^n$ denotes the input length. In $\mathsf{MCSP}$, complexity is measured by circuit size, while in $\mathsf{MKtP}$ one considers Levin's notion of time-bounded Kolmogorov complexity. (In our results, the parameters $s_1(N)$ and $s_2(N)$ are asymptotically quite close, and the problems almost coincide with their standard formulations without a gap.) We establish that for $\gapmktp[s_1,s_2]$ and $\gapmcsp[s_1,s_2]$, 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 $\mathsf{P}\neq \mathsf{NP}$.
Theorem. There exists a universal constant $c \geq 1$ for which the following hold. If there exists $\varepsilon > 0$ such that for every small enough $\beta > 0$
- [(1)] $\gapmcsp[2^{\beta n}/c n, 2^{\beta n}] \notin \mathsf{Circuit}[N^{1 + \varepsilon}]$, then $\mathsf{NP} \nsubseteq \mathsf{Circuit}[\mathsf{poly}]$.
- [(2)] $\gapmktp[2^{\beta n},\, 2^{\beta n} + cn] \notin B_2$-$\mathsf{Formula}[N^{2 + \varepsilon}]$, then $\mathsf{EXP} \nsubseteq \mathsf{Formula}[\mathsf{poly}]$.
- [(3)] $\gapmktp[2^{\beta n},\, 2^{\beta n} + cn] \notin U_2$-$\mathsf{Formula}[N^{3 + \varepsilon}]$, then $\mathsf{EXP} \nsubseteq \mathsf{Formula}[\mathsf{poly}]$.
- [(4)] $\gapmktp[2^{\beta n},\, 2^{\beta n} + cn] \notin \mathsf{BP}[N^{2 + \varepsilon}]$, then $\mathsf{EXP} \nsubseteq \mathsf{BP}[\mathsf{poly}]$.
These results are complemented by lower bounds for $\gapmcsp$ and $\gapmktp$ against different models. For instance, the lower bound assumed in (1) holds for $U_2$-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 $\gapmktp$ lies below existing lower bounds: $U_2$-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 $\gapmktp$, then $\mathsf{EXP} \nsubseteq \mathsf{NC}^1$ would follow via hardness magnification.
--------------
A conference version of this paper appeared in the Proceedings of the 34th Computational Complexity Conference (CCC'19). A preprint of this article appeared in the Electronic Colloquium on Computational Complexity (ECCC) as Tech Report TR 18-158.
Licensed under a Creative Commons Attribution License (CC-BY)