Computer Science – Computational Complexity
Scientific paper
1999-07-26
Computer Science
Computational Complexity
14 pages; to appear in Proc. FCT'99
Scientific paper
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) 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 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 EP^{NP}, no proof of membership in UP^{NP} is known. Thus, EP is indeed a tool that gives evidence against NP-completeness in natural cases where UP cannot currently be applied.
Borchert Bernd
Hemaspaandra Lane A.
Rothe Joerg
No associations
LandOfFree
Restrictive Acceptance Suffices for Equivalence Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Restrictive Acceptance Suffices for Equivalence Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Restrictive Acceptance Suffices for Equivalence Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-619322