Easiness amplification and uniform circuit lower bounds
© Cody D. Murray and R. Ryan Williams. We present new consequences of the assumption that time-bounded algorithms can be "compressed" with non-uniform circuits. Our main contribution is an "easiness amplification" lemma for circuits. One instantiation of the lemma says: if n1+ϵ-t...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137358 |
| _version_ | 1826190776472698880 |
|---|---|
| author | Williams, Richard Ryan Murray, Cody |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Williams, Richard Ryan Murray, Cody |
| author_sort | Williams, Richard Ryan |
| collection | MIT |
| description | © Cody D. Murray and R. Ryan Williams. We present new consequences of the assumption that time-bounded algorithms can be "compressed" with non-uniform circuits. Our main contribution is an "easiness amplification" lemma for circuits. One instantiation of the lemma says: if n1+ϵ-time, O (n)-space computations have n1+o(1) size (non-uniform) circuits for some ϵ > 0, then every problem solvable in polynomial time and O(n) space has n1+o(1) size (non-uniform) circuits as well. This amplification has several consequences: An easy problem without small LOGSPACE-uniform circuits. For all ϵ > 0, we give a natural decision problem General Circuit nϵ-Composition that is solvable in n1+ϵ time, but we prove that polynomial-time and logarithmic-space preprocessing cannot produce n1+o(1)-size circuits for the problem. This shows that there are problems solvable in n1+ϵ time which are not in LOGSPACE-uniform n1+o(1) size, the first result of its kind. We show that our lower bound is non-relativizing, by exhibiting an oracle relative to which the result is false. Problems without low-depth LOGSPACE-uniform circuits. For all ϵ > 0, 1 < d < 2, and e < d we give another natural circuit composition problem computable in O (n1+ϵ) time, or in O((log n)d) space (though not necessarily simultaneously) that we prove does not have SPACE[(log n)e]-uniform circuits of O(n) size and O((log n)e) depth. We also show SAT does not have circuits of O (n) size and log2-o(1) n depth that can be constructed in log2-o(1) n space. A strong circuit complexity amplification. For every ϵ > 0, we give a natural problem Circuit nϵ-Composition and show that if it has O(n)-size circuits (uniform or not), then every problem solvable in 2O(n) time and 2O( p n log n) space (simultaneously) has 2O( p n log n)- size circuits (uniform or not). We also show the same consequence holds assuming SAT has O (n)-size circuits. As a corollary, if n1.1 time computations (or O(n) nondeterministic time computations) have O (n)-size circuits, then all problems in exponential time and subexponential space (such as quantified Boolean formulas) have significantly subexponential-size circuits. This is a new connection between the relative circuit complexities of easy and hard problems. |
| first_indexed | 2024-09-23T08:45:31Z |
| format | Article |
| id | mit-1721.1/137358 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:45:31Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1373582023-03-28T19:46:57Z Easiness amplification and uniform circuit lower bounds Williams, Richard Ryan Murray, Cody Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © Cody D. Murray and R. Ryan Williams. We present new consequences of the assumption that time-bounded algorithms can be "compressed" with non-uniform circuits. Our main contribution is an "easiness amplification" lemma for circuits. One instantiation of the lemma says: if n1+ϵ-time, O (n)-space computations have n1+o(1) size (non-uniform) circuits for some ϵ > 0, then every problem solvable in polynomial time and O(n) space has n1+o(1) size (non-uniform) circuits as well. This amplification has several consequences: An easy problem without small LOGSPACE-uniform circuits. For all ϵ > 0, we give a natural decision problem General Circuit nϵ-Composition that is solvable in n1+ϵ time, but we prove that polynomial-time and logarithmic-space preprocessing cannot produce n1+o(1)-size circuits for the problem. This shows that there are problems solvable in n1+ϵ time which are not in LOGSPACE-uniform n1+o(1) size, the first result of its kind. We show that our lower bound is non-relativizing, by exhibiting an oracle relative to which the result is false. Problems without low-depth LOGSPACE-uniform circuits. For all ϵ > 0, 1 < d < 2, and e < d we give another natural circuit composition problem computable in O (n1+ϵ) time, or in O((log n)d) space (though not necessarily simultaneously) that we prove does not have SPACE[(log n)e]-uniform circuits of O(n) size and O((log n)e) depth. We also show SAT does not have circuits of O (n) size and log2-o(1) n depth that can be constructed in log2-o(1) n space. A strong circuit complexity amplification. For every ϵ > 0, we give a natural problem Circuit nϵ-Composition and show that if it has O(n)-size circuits (uniform or not), then every problem solvable in 2O(n) time and 2O( p n log n) space (simultaneously) has 2O( p n log n)- size circuits (uniform or not). We also show the same consequence holds assuming SAT has O (n)-size circuits. As a corollary, if n1.1 time computations (or O(n) nondeterministic time computations) have O (n)-size circuits, then all problems in exponential time and subexponential space (such as quantified Boolean formulas) have significantly subexponential-size circuits. This is a new connection between the relative circuit complexities of easy and hard problems. 2021-11-04T16:23:14Z 2021-11-04T16:23:14Z 2017 2021-03-30T13:22:49Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137358 Williams, Richard Ryan and Murray, Cody. 2017. "Easiness amplification and uniform circuit lower bounds." Leibniz International Proceedings in Informatics, LIPIcs, 79. en 10.4230/LIPIcs.CCC.2017.8 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Williams, Richard Ryan Murray, Cody Easiness amplification and uniform circuit lower bounds |
| title | Easiness amplification and uniform circuit lower bounds |
| title_full | Easiness amplification and uniform circuit lower bounds |
| title_fullStr | Easiness amplification and uniform circuit lower bounds |
| title_full_unstemmed | Easiness amplification and uniform circuit lower bounds |
| title_short | Easiness amplification and uniform circuit lower bounds |
| title_sort | easiness amplification and uniform circuit lower bounds |
| url | https://hdl.handle.net/1721.1/137358 |
| work_keys_str_mv | AT williamsrichardryan easinessamplificationanduniformcircuitlowerbounds AT murraycody easinessamplificationanduniformcircuitlowerbounds |