ギャップP

GapPは、すべての関数fから構成される計数複雑性クラスであり、多項式時間の非決定性チューリングマシンMが存在し、任意の入力xに対して、f(x)はMの受け入れパスの数からMの拒否パスの数を引いた値に等しくなります。GapP は、減算による#Pの閉包そのものです。また、加算、乗算、二項係数など、#P の他のすべての閉包特性も備えています。

カウントクラスAWPPは GapP 関数に基づいて定義されます。