GapP
Complexity class
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
- v
- t
- e
Complexity classes
- DLOGTIME
- AC0
- ACC0
- TC0
- L
- SL
- RL
- FL
- NL
- NL-complete
- NC
- SC
- CC
- P
- P-complete
- ZPP
- RP
- BPP
- BQP
- APX
- FP
- EXPTIME
- NEXPTIME
- EXPSPACE
- 2-EXPTIME
- ELEMENTARY
- PR
- R
- RE
- ALL
| P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e
