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
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.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK