| _version_ |
1826201804439814144
|
| collection |
MIT
|
| description |
© 2020 ACM. We establish several "sharp threshold" results for computational complexity. For certain tasks, we can prove a resource lower bound of nc for c ≥ 1 (or obtain an efficient circuit-analysis algorithm for nc size), there is strong intuition that a similar result can be proved for larger functions of n, yet we can also prove that replacing "nc" with "nc+ϵ" in our results, for any ϵ > 0, would imply a breakthrough nω(1) lower bound. We first establish such a result for Hardness Magnification. We prove (among other results) that for some c, the Minimum Circuit Size Problem for (logn)c-size circuits on length-n truth tables (MCSP[(logn)c]) does not have n2-o(1)-size probabilistic formulas. We also prove that an n2+ϵ lower bound for MCSP[(logn)c] (for any ϵ > 0 and c ≥ 1) would imply major lower bound results, such as NP does not have nk-size formulas for all k, and #SAT does not have log-depth circuits. Similar results hold for time-bounded Kolmogorov complexity. Note that cubic size lower bounds are known for probabilistic De Morgan formulas (for other functions). Next we show a sharp threshold for Quantified Derandomization (QD) of probabilistic formulas: (a) For all α, ϵ > 0, there is a deterministic polynomial-time algorithm that finds satisfying assignments to every probabilistic formula of n2-2α-ϵ size with at most 2nα falsifying assignments. (b) If for some α, ϵ > 0, there is such an algorithm for probabilistic formulas of n2-α+ϵ-size and 2nα unsatisfying assignments, then a full derandomization of NC1 follows: a deterministic poly-time algorithm additively approximating the acceptance probability of any polynomial-size formula. Consequently, NP does not have nk-size formulas, for all k. Finally we show a sharp threshold result for Explicit Obstructions, inspired by Mulmuley's notion of explicit obstructions from GCT. An explicit obstruction against S(n)-size formulas is a poly-time algorithm A such that A(1n) outputs a list {(xi,f(xi))}i g [poly(n)] g {0,1}n × {0,1}, and every S(n)-size formula F is inconsistent with the (partially defined) function f. We prove that for all ϵ > 0, there is an explicit obstruction against n2-ϵ-size formulas, and prove that there is an explicit obstruction against n2+ϵ-size formulas for some ϵ > 0 if and only if there is an explicit obstruction against all polynomial-size formulas. This in turn is equivalent to the statement that E does not have 2o(n)-size formulas, a breakthrough in circuit complexity.
|
| first_indexed |
2024-09-23T11:57:29Z
|
| format |
Article
|
| id |
mit-1721.1/137205
|
| institution |
Massachusetts Institute of Technology
|
| language |
English
|
| last_indexed |
2024-09-23T11:57:29Z
|
| publishDate |
2021
|
| publisher |
ACM
|
| record_format |
dspace
|
| spelling |
mit-1721.1/1372052022-04-01T17:27:46Z Sharp threshold results for computational complexity © 2020 ACM. We establish several "sharp threshold" results for computational complexity. For certain tasks, we can prove a resource lower bound of nc for c ≥ 1 (or obtain an efficient circuit-analysis algorithm for nc size), there is strong intuition that a similar result can be proved for larger functions of n, yet we can also prove that replacing "nc" with "nc+ϵ" in our results, for any ϵ > 0, would imply a breakthrough nω(1) lower bound. We first establish such a result for Hardness Magnification. We prove (among other results) that for some c, the Minimum Circuit Size Problem for (logn)c-size circuits on length-n truth tables (MCSP[(logn)c]) does not have n2-o(1)-size probabilistic formulas. We also prove that an n2+ϵ lower bound for MCSP[(logn)c] (for any ϵ > 0 and c ≥ 1) would imply major lower bound results, such as NP does not have nk-size formulas for all k, and #SAT does not have log-depth circuits. Similar results hold for time-bounded Kolmogorov complexity. Note that cubic size lower bounds are known for probabilistic De Morgan formulas (for other functions). Next we show a sharp threshold for Quantified Derandomization (QD) of probabilistic formulas: (a) For all α, ϵ > 0, there is a deterministic polynomial-time algorithm that finds satisfying assignments to every probabilistic formula of n2-2α-ϵ size with at most 2nα falsifying assignments. (b) If for some α, ϵ > 0, there is such an algorithm for probabilistic formulas of n2-α+ϵ-size and 2nα unsatisfying assignments, then a full derandomization of NC1 follows: a deterministic poly-time algorithm additively approximating the acceptance probability of any polynomial-size formula. Consequently, NP does not have nk-size formulas, for all k. Finally we show a sharp threshold result for Explicit Obstructions, inspired by Mulmuley's notion of explicit obstructions from GCT. An explicit obstruction against S(n)-size formulas is a poly-time algorithm A such that A(1n) outputs a list {(xi,f(xi))}i g [poly(n)] g {0,1}n × {0,1}, and every S(n)-size formula F is inconsistent with the (partially defined) function f. We prove that for all ϵ > 0, there is an explicit obstruction against n2-ϵ-size formulas, and prove that there is an explicit obstruction against n2+ϵ-size formulas for some ϵ > 0 if and only if there is an explicit obstruction against all polynomial-size formulas. This in turn is equivalent to the statement that E does not have 2o(n)-size formulas, a breakthrough in circuit complexity. 2021-11-03T14:43:38Z 2021-11-03T14:43:38Z 2020-06 2020-06 2021-04-05T13:41:17Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137205 2020. "Sharp threshold results for computational complexity." Proceedings of the Annual ACM Symposium on Theory of Computing. en 10.1145/3357713.3384283 Proceedings of the Annual ACM Symposium on Theory of Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf ACM Other repository
|
| spellingShingle |
Sharp threshold results for computational complexity
|
| title |
Sharp threshold results for computational complexity
|
| title_full |
Sharp threshold results for computational complexity
|
| title_fullStr |
Sharp threshold results for computational complexity
|
| title_full_unstemmed |
Sharp threshold results for computational complexity
|
| title_short |
Sharp threshold results for computational complexity
|
| title_sort |
sharp threshold results for computational complexity
|
| url |
https://hdl.handle.net/1721.1/137205
|