Turing machines with few accepting computations and low sets for PP
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\).
path restricted nondeterministic polynomial time machines
scientific article; zbMATH DE number 58809