Restrictive Acceptance Suffices for Equivalence Problems
<|reference_start|>Restrictive Acceptance Suffices for Equivalence Problems: 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.<|reference_end|>
@article{borchert1999restrictive,
    title={Restrictive Acceptance Suffices for Equivalence Problems},
    author={Bernd Borchert, Lane A. Hemaspaandra and Joerg Rothe},
    journal={arXiv preprint arXiv:cs/9907041},
    year={1999},
    number={Revises Friedrich-Schiller-Universit\"at Jena Technical Report
  Math/Inf/96/13},
    archivePrefix={arXiv},
    eprint={cs/9907041},
    primaryClass={cs.CC}
}