GapP
Encyclopedia
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 nice closure properties of #P, such as addition, multiplication, and binomial coefficients.
The counting class AWPP
is defined in terms of GapP functions.
Sharp-P
In computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of a nondeterministic...
under subtraction. It also has all the other nice closure properties of #P, such as addition, multiplication, and binomial coefficients.
The counting class AWPP
Almost Wide Probabilistic Polynomial-Time
In theoretical computer science, Almost Wide Probabilistic Polynomial-Time is a complexity class for problems in the context of quantum computing....
is defined in terms of GapP functions.