GapP

From Wikipedia, the free encyclopedia

You have new messages (last change).

GapP is a counting complexity class, consisting of all of the functions f such that there exists a nondeterministic polynomial-time 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 the closure of #P under subtraction[citation needed].

The counting class AWPP is defined in terms of GapP functions.

Retrieved from "http://en.wikipedia.org../../../g/a/p/GapP_71bd.html"