The Complexity of Decision Versus Search
A basic question about NP is whether or not search (the problem of finding a witness) reduces in polynomial time to decision ( the problem deciding whether there exists a witness). The fact that search does reduce to decision for SAT and other NP-complete problems (self-reducibility) is among the...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149172 |
| _version_ | 1826197845696315392 |
|---|---|
| author | Bellare, Mihir Goldwasser, Shafi |
| author_facet | Bellare, Mihir Goldwasser, Shafi |
| author_sort | Bellare, Mihir |
| collection | MIT |
| description | A basic question about NP is whether or not search (the problem of finding a witness) reduces in polynomial time to decision ( the problem deciding whether there exists a witness). The fact that search does reduce to decision for SAT and other NP-complete problems (self-reducibility) is among the most well known facts in the theory of computation. But the general question of whether search reduces to decision for every language in NP remains open. We indicate that the answer is negative: under a natural complexity assumption (that deterministic and non deterministic double exponential time are unequal) we construct a language in NP for which search does not reduce to decision. |
| first_indexed | 2024-09-23T10:54:23Z |
| id | mit-1721.1/149172 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:54:23Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491722023-03-30T03:58:10Z The Complexity of Decision Versus Search Bellare, Mihir Goldwasser, Shafi A basic question about NP is whether or not search (the problem of finding a witness) reduces in polynomial time to decision ( the problem deciding whether there exists a witness). The fact that search does reduce to decision for SAT and other NP-complete problems (self-reducibility) is among the most well known facts in the theory of computation. But the general question of whether search reduces to decision for every language in NP remains open. We indicate that the answer is negative: under a natural complexity assumption (that deterministic and non deterministic double exponential time are unequal) we construct a language in NP for which search does not reduce to decision. 2023-03-29T14:34:44Z 2023-03-29T14:34:44Z 1991-04 https://hdl.handle.net/1721.1/149172 23661279 MIT-LCS-TM-444 application/pdf |
| spellingShingle | Bellare, Mihir Goldwasser, Shafi The Complexity of Decision Versus Search |
| title | The Complexity of Decision Versus Search |
| title_full | The Complexity of Decision Versus Search |
| title_fullStr | The Complexity of Decision Versus Search |
| title_full_unstemmed | The Complexity of Decision Versus Search |
| title_short | The Complexity of Decision Versus Search |
| title_sort | complexity of decision versus search |
| url | https://hdl.handle.net/1721.1/149172 |
| work_keys_str_mv | AT bellaremihir thecomplexityofdecisionversussearch AT goldwassershafi thecomplexityofdecisionversussearch AT bellaremihir complexityofdecisionversussearch AT goldwassershafi complexityofdecisionversussearch |