Top Qs
Timeline
Chat
Perspective
GapP
Complexity class From Wikipedia, the free encyclopedia
Remove ads
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.
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (November 2024) |
The counting class AWPP is defined in terms of GapP functions.
Remove ads
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
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads