Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems

摘要

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.