文章基本信息

标题：Hardness Magnification Near State-of-the-Art Lower Bounds
本地全文：下载
作者：Igor C.Oliveira ; Ján Pich ; Rahul Santhanam 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2021
卷号：17
期号：1
页码：1-38
DOI：10.4086/toc.2021.v017a011
语种：English
出版社：University of Chicago
摘要：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.
关键词：circuit complexity; minimum circuit size problem; Kolmogorov complexity