GapP
id:
gapp-284-14600127
title:
GapP
text:
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.
brand slug:
wiki
category slug:
encyclopedia
description:
Complexity class
original url:
https://en.wikipedia.org/wiki/GapP
date created:
date modified:
2020-05-26T03:10:00Z
main entity:
{"identifier":"Q5521731","url":"https://www.wikidata.org/entity/Q5521731"}
image:
fields total:
13
integrity:
14