Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-045 | 28th August 1996 00:00

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

RSS-Feed




TR96-045
Authors: Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe
Publication: 29th August 1996 09:43
Downloads: 2236
Keywords: 


Abstract:

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.


Comment(s):

Comment #1 to TR96-045 | 10th September 1996 13:35

Comment Contact: rothe@mipool.uni-jena.de Author: Bernd Borchert and Lane A. Hemaspaandra and Joerg Rothe Comment on: TR96-045





Comment #1
Authors:
Accepted on: 10th September 1996 13:35
Downloads: 1766
Keywords: 


Abstract:


Comment #2 to TR96-045 | 23rd September 1996 13:34

A note on FewP $\subseteq$ EP Comment on: TR96-045





Comment #2
Authors: Richard Beigel
Accepted on: 23rd September 1996 13:34
Downloads: 1904
Keywords: 


Abstract:

We give an alternate proof that FewP is a subset EP.




ISSN 1433-8092 | Imprint