Introduction to Counting Classes

Our interest in nondeterministic polynomial time-bounded Turing machines has been concerned primarily with the question of whether, given an input x, there exists at least one accepting computation. However, this is not entirely so, for the definition of PP is that the majority of computations are accepting. Now we will be interested in the following classes, which use counting explicitly in their definitions.