Restrictive Acceptance Suffices for Equivalence Problems
| dc.creator | Borchert, Bernd | |
| dc.creator | Hemaspaandra, Lane A. | |
| dc.creator | Rothe, Joerg | |
| dc.date | 1999-07-26 | |
| dc.date.accessioned | 2026-07-07T03:24:16Z | |
| dc.date.available | 2026-07-07T03:24:16Z | |
| dc.description | 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. | |
| dc.description | 14 pages; to appear in Proc. FCT'99 | |
| dc.identifier | https://arxiv.org/abs/cs/9907041 | |
| dc.identifier | http://arxiv.org/abs/cs/9907041 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33263 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | Restrictive Acceptance Suffices for Equivalence Problems | |
| dc.type | text |