ART

GapP is a counting complexity class, consisting of all of the functions f such that there exists a polynomial-time non-deterministic Turing machine M where, for any input x, f(x) is equal to the number of accepting paths of M minus the number of rejecting paths of M. GapP is exactly the closure of #P under subtraction. It also has all the other closure properties of #P, such as addition, multiplication, and binomial coefficients.

The counting class AWPP is defined in terms of GapP functions.
References

S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes, Journal of Computer and System Sciences 48(1):116-148, 1994.
Complexity Zoo: GapP

Important complexity classes (more)
Considered feasible

DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P
P-complete ZPP RP BPP BQP APX

Suspected infeasible

UP NP
NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P
#P-complete IP PSPACE
PSPACE-complete

Considered infeasible

EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL

Class hierarchies

Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy

Families of classes

DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License