We study 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. 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 seems incomparable with the previous SPP upper bound.
Finally, we show that EP can be viewed as the promise-class analog of
C_=P.
We give an alternate proof that FewP is a subset EP.
