Encyclopedia > G > GapP
GapP
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.
Information are taken from Wikipedia, the open encyclopedia, to which contribute many volunteers from around the whole world. Texts are available under the following conditions GNU Free Documentation License.
Encyklopedie (cz) Encyklopédia (sk) Enzyklopädie (de)