ZPP

Материал из DISCOPAL
Перейти к: навигация, поиск

Класс сложности ZPP (Zero-Probability Polynomial-time) можно определить, как пересечение классов RP и coRP:

или, через самостоятельное определение:

Класс сложности ZPP состоит из всех языков L для которых существует полиномиальная вероятностная машина Тьюринга M, возвращающая только ответы «0», «1», «не знаю», причем::


Диаграмма «ближайших» классов

[svg]