Promise problems complete for complexity classes

AbstractA 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 ≤dP-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