期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
