ZPP

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

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

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.