  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 more broadly applicable---to suggesting that
concrete~NP problems are not NP-complete. In particular we introduce the class
EP, the subclass of NP consisting of those languages accepted by NP machines
that when they accept always have a number of accepting paths that is a power
of two. Since if any NP-complete set is in EP then all NP sets are in EP, it
follows---with whatever degree of strength one believes that EP differs from
NP---that membership in EP can be viewed as evidence that a problem is not
NP-complete.
  We show that the negation equivalence problem for OBDDs (ordered binary
decision diagrams) and the interchange equivalence problem for 2-dags are in
EP. We also show that for boolean negation the equivalence problem is in
EP^{NP}, thus tightening the existing NP^{NP} upper bound. We show that FewP,
bounded ambiguity polynomial time, is contained in EP, a result that is not
known to follow from the previous SPP upper bound. For the three problems and
classes just mentioned with regard to EP, no proof of membership/containment in
UP is known, and for the problem just mentioned with regard to EP^{NP}, no
proof of membership in UP^{NP} is known. Thus, EP is indeed a tool that gives
evidence against NP-completeness in natural cases where UP cannot currently be
applied.
