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, 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.

References

This article is issued from Wikipedia - version of the 9/22/2010. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.