THE COMPLEXITY OF DECISION VERSUS SEARCH

A basic question about NP is whether or not search reduces in polynomi al time to decision. This paper indicates that the answer is negative: Under a complexity assumption (that deterministic and nondeterministi c double-exponential time are unequal) a language in NP for which sear ch does not reduce to decision is constructed. These ideas extend in a natural way to interactive proofs and program checking. Under similar assumptions, the authors present languages in NP for which it is hard er to prove membership interactively than it is to decide this members hip, and languages in NP that are not checkable.