文章基本信息

标题：Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems
本地全文：下载
作者：Bernd Borchert ; Lane A. Hemaspaandra ; Jörg Rothe 等
期刊名称：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.