ECCC-Report TR18-158https://eccc.weizmann.ac.il/report/2018/158Comments and Revisions published for TR18-158en-usSat, 01 Dec 2018 06:32:22 +0200
Revision 1
| Hardness magnification near state-of-the-art lower bounds |
Igor Carboni Oliveira,
Ján Pich,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2018/158#revision1This work continues the development of hardness magnification. The latter proposes a 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 super-polynomial lower bounds.
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. Gap-MCSP$[2^{\beta n}/c n, 2^{\beta n}] \notin$Circuit$[N^{1 + \varepsilon}]$, then NP is not contained in Circuit[poly].
2. Gap-MKtP$[2^{\beta n},\, 2^{\beta n } + cn] \notin$TC$^0[N^{1 + \varepsilon}]$, then EXP is not contained in TC$^0$[poly].
3. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin B_2$-Formula$[N^{2 + \varepsilon}]$, then EXP is not contained in Formula[poly].
4. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin U_2$-Formula$[N^{3 + \varepsilon}]$, then EXP is not contained in Formula[poly].
5. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin$BP$[N^{2 + \varepsilon}]$, then EXP is not contained in BP[poly].
6. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin$(AC$^0[6])[N^{1 + \varepsilon}]$, then EXP is not contained in AC$^0[6]$.
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 (3)-(5) hold for various regimes of parameters.
Going beyond the standard boolean devices, we 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 is not contained in NC$^1$ would follow via hardness magnification.Sat, 01 Dec 2018 06:32:22 +0200https://eccc.weizmann.ac.il/report/2018/158#revision1
Paper TR18-158
| Hardness magnification near state-of-the-art lower bounds |
Igor Carboni Oliveira,
Ján Pich,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2018/158This work continues the development of hardness magnification. The latter proposes a 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 super-polynomial lower bounds.
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. Gap-MCSP$[2^{\beta n}/c n, 2^{\beta n}] \notin$Circuit$[N^{1 + \varepsilon}]$, then NP is not contained in Circuit[poly].
2. Gap-MKtP$[2^{\beta n},\, 2^{\beta n } + cn] \notin$TC$^0[N^{1 + \varepsilon}]$, then EXP is not contained in TC$^0$[poly].
3. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin B_2$-Formula$[N^{2 + \varepsilon}]$, then EXP is not contained in Formula[poly].
4. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin U_2$-Formula$[N^{3 + \varepsilon}]$, then EXP is not contained in Formula[poly].
5. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin$BP$[N^{2 + \varepsilon}]$, then EXP is not contained in BP[poly].
6. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin$(AC$^0[6])[N^{1 + \varepsilon}]$, then EXP is not contained in AC$^0[6]$.
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 (3)-(5) hold for various regimes of parameters.
Going beyond the standard boolean devices, we 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 is not contained in NC$^1$ would follow via hardness magnification.Tue, 11 Sep 2018 17:48:03 +0300https://eccc.weizmann.ac.il/report/2018/158