GapP
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
GAPP may refer to: * General Administration of Press and Publication * Generally Accepted Privacy Principles, framework for accountants to help manage privacy concerns * German American Partnership Program * Geometric-Arithmetic Parallel Processor * GapP, A complexity class of counting in computer science
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, the value 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. The counting class AWPP is defined in terms of GapP functions. ==References== S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes, Journal of Computer and System Sciences 48(1):116-148, 1994.
Text derived from https://en.wikipedia.org/w/index.php?oldid=598291466 under CC BY-SA 4.0; modifications have been made.