GapP

From Wikipedia, the free encyclopedia

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]}.