GapP

ОПП является классом сложности подсчета , состоящий из всех функций F , таких , что существует полиномиальный недетерминированная Тьюринга машина М , где, для любого входного х , F (X) равно числу принимающих путей М минус количество отклоняя пути М . GapP - это в точности закрытие #P при вычитании. Он также имеет все другие свойства замыкания #P, такие как сложение, умножение и биномиальные коэффициенты.

Счетный класс AWPP определяется в терминах функций GapP.

Ссылки [ править ]

• С. Феннер, Л. Фортноу и С. Курц. Щелевые Определяемые классы подсчета , Журнал вычислительной техники и системы наук 48 (1): 116-148, 1994.
• Зоопарк сложности : GapP