Turing machines with few accepting computations and low sets for PP (Q1190987): Difference between revisions

Complexity classes, defined using the idea of bounding the number of accepting paths of a nondeterministic Turing machine, were introduced with the hope that perhaps they represent more tractable subclasses of the class \(NP\). The paper investigates some properties of the path- restricted class \(Few\), which includes also other known classes of this type, i.e. \(UP\) and \(FewP\). It is shown that for every language in this class there exists a polynomial time nondeterministic machine that has exactly \(f(x) + 1\) accepting paths for strings in the language, and \(f(x)\) accepting paths otherwise (for a polynomial time computable function \(f\)). This result is then used to prove that \(Few\) is low for the complexity classes \(PP\), \(\oplus P\), and \textit{exact counting}, i.e. an oracle from \(Few\) does not increase computational power of machines from these classes. Lowness for \(PP\) is shown also for sets from the class \(BPP\) and sparse sets in \(NP\).