Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Restrictive acceptance suffices for equivalence problems
| |
|
Restrictive acceptance suffices for equivalence problems
Bernd Borchert6, Lane A. Hemaspaandra7 and Jörg Rothe8 
| (6) |
Mathematisches Institut, Universität Heidelberg, 69120 Heidelberg, Germany |
| (7) |
Dept. of Computer Science, University of Rochester, Rochester, NY 14627, USA |
| (8) |
Institut für Informatik, Friedrich-Schiller-Universität Jena, 07740 Jena, Germany |
Abstract
One way of suggesting that an NP problem may not be NP-complete is to show that it is in the class UP. We suggest an analogous
new approach—weaker in strength of evidence but more broadly applicable—to suggesting that concrete NP problems are not NP-complete.
In particular we introduce the class 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. Since if any NP-complete set is in EP then all
NP sets are in EP, it follows—with whatever degree of strength one believes that EP differs from NP—that membership in EP
can be viewed as evidence that a problem is not NP-complete.
We show that the negation equivalence problem for OBDDs (ordered binary decision diagrams [17,12]) and the interchange equivalence
problem for 2-dags are in EP. We also show that for boolean negation [20] the equivalence problem is in EPNP, thus tightening
the existing NPNP upper bound. We show that FewP [2], bounded ambiguity polynomial time, is contained in EP, a result that is not known to
follow from the previous SPP upper bound. For the three problems and classes just mentioned with regard to EP, no proof of
membership/containment in UP is known, and for the problem just mentioned with regard to EPNP, no proof of membership in UPNP is known. Thus, EP is indeed a tool that gives evidence against NP-completeness in natural cases where UP cannot currently
be applied.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|