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
    0 references
    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

    Identifiers