Promise problems complete for complexity classes

A general framework is given to obtain hardness results for promise problems that derive from self-reducible decision problems. The principal theorem is that if a set A is ≤ d P -equivalent to a disjunctive-self-reducible set in NP, then the natural promise problem associated with A is as hard to solve as it is to recognize A. NP-hardness of the satisfiability promise problem follows, and graph isomorphism hardness of a promise problem that derives from the graph isomorphism problem is proved.

Authors

• Alan L. Selman

Keywords

No keywords are indexed for this paper.