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 |