Turing machines with few accepting computations and low sets for PP. (English) Zbl 0757.68056

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 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\).


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI


[1] Allender, E.W., Invertible functions, ()
[2] Balcázar, J.L.; Book, R.V.; Schöning, U., The polynomial-time hierarchy and sparse oracles, J. assoc. comput. Mach, 33, 603-617, (1986) · Zbl 0625.68033
[3] Beigel, R., Relativized counting classes: relations among thresholds, parity, and mods. TR 88-09, (Sept. 1988), The Johns Hopkins University Baltimore
[4] Beigel, R.; Hemachandra, L.A.; Wechsung, G., P^{NP[log]}\( (̄\) PP, (), 225-227
[5] Book, R.; Long, T.J.; Selman, A., Quantitative relativizations of complexity classes, SIAM J. comput., 13, 461-487, (1984) · Zbl 0599.03041
[6] Cai, J.; Hemachandra, L.A., On the power of parity, (), 229-240
[7] Gill, J., Computational complexity of probabilistic complexity classes, SIAM J. comput., 6, 675-695, (1977) · Zbl 0366.02024
[8] Grollmann, S.; Selman, A.L., Complexity measures for public-key crypto-systems, (), 495-503
[9] Ko, K.I.; Schöning, U., On circuit-size complexity and the low hierarchy in NP, SIAM J. comput., 14, 41-51, (1986) · Zbl 0562.68033
[10] Long, T.J.; Selman, A.L., Relativizing complexity classes with sparse sets, J. assoc. comput. Mach., 33, 618-628, (1986)
[11] Mahaney, S.A., Sparse complete sets for NP: solution of a conjecture of berman and hartmanis, J. comput. system sci., 25, 130-143, (1982) · Zbl 0493.68043
[12] Papadimitriou, C.H.; Zachos, S.K., Two remarks on the power of counting, (), 269-276
[13] Schöning, U., A low and a high hierarchy within NP, J. comput. system sci., 27, 14-28, (1983)
[14] Schöning, U., Complexity and structure, () · Zbl 0872.68048
[15] Schöning, U., The power of counting, (), 2-9
[16] S. {\scTODA}, Restricted relativizations of probabilistic polynomial time, Theoret. Comput. Sci., to appear. · Zbl 0749.68038
[17] Torán, J., Structural properties of the counting hierarchies, ()
[18] Torán, J., An oracle characterization of the counting hierarchy, (), 213-223
[19] Valiant, L.G., The relative complexity of checking and evaluating, Inform. process. lett., 5, 20-23, (1976) · Zbl 0342.68028
[20] Valiant, L.G., The complexity of computing the permanent, Theoret. comput. sci., 8, 410-421, (1979) · Zbl 0415.68008
[21] Wagner, K.W., The complexity of combinatorial problems with succinct input representation, Acta inform., 23, 325-356, (1986) · Zbl 0621.68032
[22] Zachos, S.; Heller, H., A decisive characterization of BPP, Inform. and control, 69, 125-135, (1986) · Zbl 0616.68049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.