Hardness magnification near state-of-the-art lower bounds
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. <br> We consider gap versions...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2021
|
| _version_ | 1826307560473362432 |
|---|---|
| author | Oliveira, IC Pich, J Santhanam, R |
| author_facet | Oliveira, IC Pich, J Santhanam, R |
| author_sort | Oliveira, IC |
| collection | OXFORD |
| description | 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.
<br>
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.
<br>
Theorem. There exists a universal constant c≥1 for which the following hold. If there exists ε>0 such that for every small enough β>0
<br>[(1)] Gap−MCSP[2βn/cn,2βn]∉Circuit[N1+ε], then NP⊈Circuit[poly].
<br>[(2)] Gap−MKtP[2βn,2βn+cn]∉B2-Formula[N2+ε], then EXP⊈Formula[poly].
<br>[(3)] Gap−MKtP[2βn,2βn+cn]∉U2-Formula[N3+ε], then EXP⊈Formula[poly].
<br>[(4)] Gap−MKtP[2βn,2βn+cn]∉BP[N2+ε], then EXP⊈BP[poly].
<br>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.
<br>
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. |
| first_indexed | 2024-03-07T07:04:57Z |
| format | Journal article |
| id | oxford-uuid:8e2b9200-c137-4b91-bb10-805f93eb2cf6 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:04:57Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | oxford-uuid:8e2b9200-c137-4b91-bb10-805f93eb2cf62022-04-25T13:08:44ZHardness magnification near state-of-the-art lower boundsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:8e2b9200-c137-4b91-bb10-805f93eb2cf6EnglishSymplectic Elements2021Oliveira, ICPich, JSanthanam, RThis 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. <br> 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. <br> Theorem. There exists a universal constant c≥1 for which the following hold. If there exists ε>0 such that for every small enough β>0 <br>[(1)] Gap−MCSP[2βn/cn,2βn]∉Circuit[N1+ε], then NP⊈Circuit[poly]. <br>[(2)] Gap−MKtP[2βn,2βn+cn]∉B2-Formula[N2+ε], then EXP⊈Formula[poly]. <br>[(3)] Gap−MKtP[2βn,2βn+cn]∉U2-Formula[N3+ε], then EXP⊈Formula[poly]. <br>[(4)] Gap−MKtP[2βn,2βn+cn]∉BP[N2+ε], then EXP⊈BP[poly]. <br>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. <br> 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. |
| spellingShingle | Oliveira, IC Pich, J Santhanam, R Hardness magnification near state-of-the-art lower bounds |
| title | Hardness magnification near state-of-the-art lower bounds |
| title_full | Hardness magnification near state-of-the-art lower bounds |
| title_fullStr | Hardness magnification near state-of-the-art lower bounds |
| title_full_unstemmed | Hardness magnification near state-of-the-art lower bounds |
| title_short | Hardness magnification near state-of-the-art lower bounds |
| title_sort | hardness magnification near state of the art lower bounds |
| work_keys_str_mv | AT oliveiraic hardnessmagnificationnearstateoftheartlowerbounds AT pichj hardnessmagnificationnearstateoftheartlowerbounds AT santhanamr hardnessmagnificationnearstateoftheartlowerbounds |