Restrictive Acceptance Suffices for Equivalence Problems

Bernd Borchert, Lane A. Hemaspaandra, Joerg Rothe

One way of suggesting that an NP problem may not be NP-complete is to show that it is in the class UP. We suggest an analogous new approach---weaker in strength of evidence but mor…