GapP - GapP - Wikipedia

GapP je třída složitosti počítání, skládající se ze všech funkcí F takové, že existuje polynomiální čas nedeterministický Turingův stroj M kde pro jakýkoli vstup X, f (x) se rovná počtu přijímajících cest M minus počet odmítajících cest z M. GapP je přesně uzávěrka #P odečteno. Má také všechny ostatní uzavírací vlastnosti #P, jako je sčítání, násobení a binomické koeficienty.

Počítání třída AWPP je definován z hlediska funkcí GapP.

Reference