Counting classes: Thresholds, parity, mods, and fewness (Q5905584)

Counting classes consist of languages defined in terms of the number of accepting computations of nondeterministic polynomial-time Turing machines. Well known examples of counting classes are NP, co-NP, PARITYP, and PP. Every counting class is a subset of \(P^{\# P[1]}\), the class of languages computable in polynomial time using a single call to an oracle capable of determining the number of accepting paths of an NP machine. The paper uses polynomials to obtain closure properties of \(\#P\). Although some of the closure properties have been reported as folklore, especially in the circuits community, this paper presents the first systematic development of the technique, which has increased in popularity among complexity theorists studying counting classes and circuits. Using closure properties of \(\#P\), the paper develops a complexity theory for counting classes defined in terms of thresholds and moduli. One unexpected result is that \(\text{MOD}_{k^ i}P=\text{MOD}_ kP\) for prime \(k\). The paper also improves a result of \textit{J. Cai} and \textit{L. Hemachandra} [Math. Syst. Theory 23, 95-106 (1990; Zbl 0718.68038)] by showing that recognizing languages in the class Few is as easy as distinguishing uniquely satisfiable formulas from unsatisfiable formulas (or detecting unique solutions, á la \textit{L. Valiant} and \textit{V. Vazirani} [Theor. Comp. Sci. 47, 85-95 (1986; Zbl 0621.68030)]).