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 Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
