GapP: Difference between revisions
Content deleted Content added
removed "nice" |
Added {{No footnotes}} tag |
||
| Line 1: | Line 1: | ||
{{short description|Complexity class}} |
{{short description|Complexity class}} |
||
{{No footnotes|date=November 2024}} |
|||
'''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 [[Sharp-P|#P]] under subtraction. It also has all the other closure properties of #P, such as addition, multiplication, and binomial coefficients. |
'''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 [[Sharp-P|#P]] under subtraction. It also has all the other closure properties of #P, such as addition, multiplication, and binomial coefficients. |
||
Latest revision as of 07:24, 18 November 2024
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (November 2024) |
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 closure properties of #P, such as addition, multiplication, and binomial coefficients.
The counting class AWPP is defined in terms of GapP functions.
References
[edit]- S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes, Journal of Computer and System Sciences 48(1):116-148, 1994.
- Complexity Zoo: GapP