Counting classes: Thresholds, parity, mods, and fewness (Q5905584): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(92)90084-s / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1736584826 / rank | |||
Normal rank |
Latest revision as of 10:55, 30 July 2024
scientific article; zbMATH DE number 94450
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting classes: Thresholds, parity, mods, and fewness |
scientific article; zbMATH DE number 94450 |
Statements
Counting classes: Thresholds, parity, mods, and fewness (English)
0 references
16 January 1993
0 references
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)]).
0 references
counting classes
0 references
MOD\(_ k P\)
0 references
PARITYP
0 references
PP
0 references
polynomial time
0 references
polynomials
0 references
\(\#P\)
0 references
Few
0 references
unique solutions
0 references