ZPP (сложность)
-
Определение и свойства ZPP
- ZPP — это класс задач, решаемых вероятностными машинами Тьюринга с ожидаемым полиномиальным временем выполнения.
- Алгоритм Лас-Вегаса для задач в ZPP всегда возвращает правильный ответ и имеет полиномиальное время выполнения.
- ZPP эквивалентен пересечению классов RP и co-RP, что можно доказать с помощью алгоритмов Лас-Вегаса.
-
Доказательства и свидетели
- Верификатор V для множества X принимает строки w, если x ∈ X, и отклоняет их, если x ∉ X.
- В ZPP любая случайная строка может быть свидетелем наличия или отсутствия x в X.
- RP и co-RP требуют наличия свидетеля, в то время как ZPP требует свидетеля для любого случая.
-
Связь с другими классами сложности
- ZPP замкнут по дополнению и равен co-ZPP.
- ZPP содержит RP и co-RP и является подмножеством P.
- Существует оракул, относительно которого ZPP равен EXPTIME, что может указывать на равенство P и ZPP.
Полный текст статьи: