Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
We prove that if every problem in NP has nk-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier’s search space has an nO(k3)size witness circuit: a witness for x that can be encoded with a circuit of only nO(k3) size....
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/130542 |
| _version_ | 1811081556662419456 |
|---|---|
| author | Murray, Cody (Cody Daniel) Williams, R Ryan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Murray, Cody (Cody Daniel) Williams, R Ryan |
| author_sort | Murray, Cody (Cody Daniel) |
| collection | MIT |
| description | We prove that if every problem in NP has nk-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier’s search space has an nO(k3)size witness circuit: a witness for x that can be encoded with a circuit of only nO(k3) size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., NQP = NTIME nlogO(1) n . This significantly extends the Easy Witness Lemma of Impagliazzo, Kabanets, and Wigderson [JCSS’02] which only held for larger nondeterministic classes such as NEXP. As a consequence, the connections between circuit-analysis algorithms and circuit lower bounds can be considerably sharpened: algorithms for approximately counting satisfying assignments to given circuits which improve over exhaustive search can imply circuit lower bounds for functions in NQP, or even NP. To illustrate, applying known algorithms for satisfiability of ACC ◦ THR circuits [R. Williams, STOC 2014] we conclude that for every fixed k, NQP does not have nlogk n-size ACC ◦ THR circuits. |
| first_indexed | 2024-09-23T11:48:30Z |
| format | Article |
| id | mit-1721.1/130542 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:48:30Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1305422022-10-01T06:10:09Z Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP Murray, Cody (Cody Daniel) Williams, R Ryan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory We prove that if every problem in NP has nk-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier’s search space has an nO(k3)size witness circuit: a witness for x that can be encoded with a circuit of only nO(k3) size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., NQP = NTIME nlogO(1) n . This significantly extends the Easy Witness Lemma of Impagliazzo, Kabanets, and Wigderson [JCSS’02] which only held for larger nondeterministic classes such as NEXP. As a consequence, the connections between circuit-analysis algorithms and circuit lower bounds can be considerably sharpened: algorithms for approximately counting satisfying assignments to given circuits which improve over exhaustive search can imply circuit lower bounds for functions in NQP, or even NP. To illustrate, applying known algorithms for satisfiability of ACC ◦ THR circuits [R. Williams, STOC 2014] we conclude that for every fixed k, NQP does not have nlogk n-size ACC ◦ THR circuits. National Science Foundation (U.S.). Career (Award CCF-1552651) 2021-04-28T17:29:38Z 2021-04-28T17:29:38Z 2018-06 2021-04-06T18:12:39Z Article http://purl.org/eprint/type/JournalArticle 9781450355599 0277-0261 https://hdl.handle.net/1721.1/130542 Murray, Cody D. and R. Ryan Williams. “Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP.” Paper in the Proceedings of the Annual ACM Symposium on Theory of Computing, June-2018, STOC 2018: 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA,, June 25-29 2018, Association for Computing Machinery (ACM): 890–901 © 2018 The Author(s) en 10.1145/3188745.3188910 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 Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Murray, Cody (Cody Daniel) Williams, R Ryan Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP |
| title | Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP |
| title_full | Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP |
| title_fullStr | Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP |
| title_full_unstemmed | Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP |
| title_short | Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP |
| title_sort | circuit lower bounds for nondeterministic quasi polytime an easy witness lemma for np and nqp |
| url | https://hdl.handle.net/1721.1/130542 |
| work_keys_str_mv | AT murraycodycodydaniel circuitlowerboundsfornondeterministicquasipolytimeaneasywitnesslemmafornpandnqp AT williamsrryan circuitlowerboundsfornondeterministicquasipolytimeaneasywitnesslemmafornpandnqp |