LCS Publication Details
Publication Title: THE COMPLEXITY OF DECISION VERSUS SEARCH
Publication Author: Bellare, Mihir
Additional Authors: Goldwasser, Shafi
LCS Document Number: MIT-LCS-TM-444
Publication Date: 4-1-1991
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
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.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.