ГэпП
GapP — это класс сложности подсчета , состоящий из всех функций f таких, что существует недетерминированная машина Тьюринга M с полиномиальным временем , где для любого входа f x (x) равно числу принимающих путей M минус число отвергающих путей M . GapP — это в точности замыкание #P при вычитании. Он также обладает всеми другими свойствами замыкания #P, такими как сложение, умножение и биномиальные коэффициенты.
Класс подсчета AWPP определяется с помощью функций GapP.
Ссылки
[ редактировать ]- С. Феннер, Л. Фортноу и С. Курц. Классы подсчета, определяемые пробелами , Журнал компьютерных и системных наук 48(1):116-148, 1994.
- Зоопарк сложности : GapP