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, (Ph.D. dissertation (1985), Georgia Institute of Technology)
[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: The Johns Hopkins University Baltimore
[4] Beigel, R.; Hemachandra, L. A.; Wechsung, G., \(P^{NP[log]} (̄\) PP, (Proceedings, 4th Structure in Complexity Theory Conf, IEEE (1989)), 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, (Symp. Theor. Aspects of Comput. Sci.. Symp. Theor. Aspects of Comput. Sci., Lecture Notes in Computer Science (1989), Springer-Verlag: Springer-Verlag New York/Berlin), 229-240 · Zbl 1492.68054
[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, (IEEE, 25th Symp. Found. Comput. Sci. (1984)), 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, (6th GI Conf. on Theor. Comput. Sci.. 6th GI Conf. on Theor. Comput. Sci., 1983. 6th GI Conf. on Theor. Comput. Sci.. 6th GI Conf. on Theor. Comput. Sci., 1983, Lecture Notes in Computer Science, Vol. 145 (1983), Springer-Verlag: Springer-Verlag New York/Berlin), 269-276 · Zbl 0506.68039
[13] Schöning, U., A low and a high hierarchy within NP, J. Comput. System Sci., 27, 14-28 (1983) · Zbl 0515.68046
[14] Schöning, U., Complexity and Structure, (Lecture Notes in Computer Science, Vol. 211 (1985), Springer-Verlag: Springer-Verlag New York/Berlin) · Zbl 0872.68048
[15] Schöning, U., The power of counting, (Proceedings, 3rd IEEE, Structure in Complexity Theory Conf. (1988)), 2-9
[16] S. TODA, Restricted relativizations of probabilistic polynomial time, Theoret. Comput. Sci., to appear.; S. TODA, Restricted relativizations of probabilistic polynomial time, Theoret. Comput. Sci., to appear. · Zbl 0749.68038
[17] Torán, J., Structural Properties of the Counting Hierarchies, (Doctoral dissertation (Jan. 1988), Facultat d’Informatica: Facultat d’Informatica UPC Barcelona)
[18] Torán, J., An oracle characterization of the counting hierarchy, (Proceedings, IEEE, Struct. Complexity Theory Conf. (1988)), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.