Theory of Computing
-------------------
Title : Hardness Magnification Near State-of-the-Art Lower Bounds
Authors : Igor C. Oliveira, Jan Pich, and Rahul Santhanam
Volume : 17
Number : 11
Pages : 1-38
URL : http://www.theoryofcomputing.org/articles/v017a011
Abstract
--------
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 $\leq s_1(N)$ from
instances of complexity $\geq s_2(N)$, and $N = 2^n$ 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 $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 Gap-MKtP[s_1,s_2] and Gap-MCSP[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 $P \neq NP$.
Theorem. There exists a universal constant $c \geq
1$ for which the following hold. If there exists $\epsilon > 0$
such that for every small enough $\beta > 0$
* [(1)] Gap-MCSP$[2^{\beta n}/c n, 2^{\beta n}] \notin
Circuit[N^{1 + \epsilon}]$, then $NP \nsubseteq Circuit[poly]$.
* [(2)] Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin
B_2-Formula[N^{2 + \epsilon}]$, then $EXP \nsubseteq Formula[poly]$.
* [(3)] Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin
U_2-Formula[N^{3 + \epsilon}]$, then $EXP \nsubseteq Formula[\mathsf{poly}]$.
* [(4)] Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin
BP[N^{2 + \epsilon}]$, then $EXP \nsubseteq BP[\mathsf{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 $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 Gap-MKtP 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 Gap-MKtP, then $EXP \nsubseteq 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 TR18-158.