##
**Counting the number of solutions. A survey of recent inclusion results in the area of counting classes.**
*(English)*
Zbl 0733.68035

Mathematical foundations of computer science, Proc. 15th Symp., MFCS ’90, Banská Bystrica/Czech. 1990, Lect. Notes Comput. Sci. 452, 121-134 (1990).

Summary: [For the entire collection see Zbl 0731.00026.]

We study classes of sets which are low for PP, and show that complexity classes defined by machines with a bounded number of solutions (Few classes) have this property J. Köbler, U. Schöning, S. Toda, J. Torán [Turing machines with few accepting computations and low sets for PP. Proc. 4th Structure in Complexity Theory Conference IEEE, 208-216 (1989)]. We prove that the bounded error probability class BPP is also low for PP [loc. cit.]. We give a characterization of the class \(P^{NP[\log]}\) in terms of “fewness” which can be used to show the inclusion \(P^{NP[\log]}\subseteq PP\) [R. Beigel, L. Hemachandra and G. Wechsung [On the power of probabilistic polynomial time. Proc. 4th Structure in Complexity Theory Conference, IEEE, 225-230 (1989)]]. Finally we study low classes for \(P^{PP}\) and obtain that \(\oplus P\) and NP fall into this category. A direct consequence of this fact is the surprising result by Toda which says that all classes in the PH are included in \(P^{PP}\) S. Toda [On the computational power of PP and \(\oplus P\), Proc. 30th FOCS Conference, 514-519 (1989)].

We study classes of sets which are low for PP, and show that complexity classes defined by machines with a bounded number of solutions (Few classes) have this property J. Köbler, U. Schöning, S. Toda, J. Torán [Turing machines with few accepting computations and low sets for PP. Proc. 4th Structure in Complexity Theory Conference IEEE, 208-216 (1989)]. We prove that the bounded error probability class BPP is also low for PP [loc. cit.]. We give a characterization of the class \(P^{NP[\log]}\) in terms of “fewness” which can be used to show the inclusion \(P^{NP[\log]}\subseteq PP\) [R. Beigel, L. Hemachandra and G. Wechsung [On the power of probabilistic polynomial time. Proc. 4th Structure in Complexity Theory Conference, IEEE, 225-230 (1989)]]. Finally we study low classes for \(P^{PP}\) and obtain that \(\oplus P\) and NP fall into this category. A direct consequence of this fact is the surprising result by Toda which says that all classes in the PH are included in \(P^{PP}\) S. Toda [On the computational power of PP and \(\oplus P\), Proc. 30th FOCS Conference, 514-519 (1989)].

### MSC:

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |