GapP

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, the value 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

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by adding missing information.

v t e Complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ REG TC TC⁰ L SL RL FL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete TFNP FNP AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY NONELEMENTARY PR R RE ALL
Other complexity classes	polyL QP
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
List of complexity classes

This page was redesigned at the edge.

References