Abstract | ||
---|---|---|
This work continues the development of hardness magnification. The latter 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 <= s(1)(N) from instances of complexity <= 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 >= 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) /cn, 2(beta n)] is not an element of Circuit [N1+epsilon], then NP not subset of Circuit[poly]. (2) Gap-MKtP [2(beta n) , 2(beta n) + cn] is not an element of TC degrees [N1+epsilon], then EXP not subset of TC0[poly]. (3) Gap-MKtP [2(beta n) , 2(beta n) + cn] is not an element of B-2-Formula [N2+epsilon], then EXP not subset of Formula[poly]. (4) Gap-MKtP [2(beta n) , 2(beta n) + cn] is not an element of U-2-Formula [N3+epsilon], then EXP not subset of Formula[poly]. (5) Gap-MKtP [2(beta n) , 2(beta n) + cn] is not an element of BP[N2+epsilon], then EXP not subset of BP[poly]. (6) Gap-MKtP [2(beta n) , 2(beta n) + cn] is not an element of (AC(0)[6])[N1+epsilon], then EXP not subset of 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. 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 not subset of NC1 would follow via hardness magnification. |
Year | DOI | Venue |
---|---|---|
2018 | 10.4230/LIPIcs.CCC.2019.27 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
Circuit Complexity,Minimum Circuit Size Problem,Kolmogorov Complexity | Discrete mathematics,Magnification,Mathematics | Journal |
Volume | ISSN | Citations |
137 | 1868-8969 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Igor Carboni Oliveira | 1 | 26 | 11.11 |
Ján Pich | 2 | 6 | 4.52 |
Rahul Santhanam | 3 | 2 | 2.76 |