Jump to content

GapP

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by R'n'B (talk | contribs) at 15:35, 22 September 2010 (Disambiguate AWPP to Almost Wide Probabilistic Polynomial-Time using popups). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

P ≟ NP 

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=GapP&oldid=386335524"