В теорії обчислювальної складності, ZPP (zero-error probabilistic polynomial time - безпомилковий імовірнісний поліноміальний) це такий клас задач, для яких існує імовірнісна машина Тьюринга, яка задовольняє декільком властивостям:

  • Вона завжди правильно відповідає "Так" або "Ні".
  • Час роботи такої машини необмежено, але математичне сподівання часу роботи полиномиальное.

Існує альтернативний набір властивостей:

  • Машина Тьюринга завжди працює за поліноміальний час.
  • Вона відповідає "Так", "Ні" або "Не знаю".
  • Відповідь може бути або правильним, або "Не знаю".
  • Якщо правильну відповідь "Так", машина Тьюринга відповідає "Так" з вірогідністю не менше .
  • Якщо правильну відповідь "Ні", машина Тьюринга відповідає "Ні" з вірогідністю не менше .

Обидва набори властивостей еквівалентні.

Машину Тюрінга, що задовольняє цим властивостям, називають іноді машиною Тьюринга типу Лас-Вегас.


Визначення через перетин

Клас ZPP в точності еквівалентний перетинанню класів RP і Co-RP. Часто саме це приймається за визначення ZPP. Щоб продемонструвати це, зауважимо, що будь-яка задача належить одночасно RP і co-RP має алгоритм типу Лас-Вегас:

  • Припустимо є мова L розпізнаваний RP алгоритмом A і (можливо абсолютно іншим) co-RP алгоритмом B.
  • Запустимо A на вхідній послідовності. Якщо він відповість "Так", то остаточну відповідь має бути "Так". В іншому випадку запустимо B з тим же входом. Якщо він відповість "Ні", то остаточну відповідь має бути "Ні". Якщо не виконано жодне з попередніх, повторимо даний крок.

Зауважимо, що лише один з алгоритмів A або B може дати неправильну відповідь, і ймовірність цієї події дорівнює на кожному кроці 50%. Т.ч. ймовірність досягти k-го кроку зменшується експоненціально щодо k. Це показує, що математичне очікування часу роботи полиномиальное. Зі сказаного випливає, що перетин RP і co-RP міститься в ZPP.

Покажемо, що ZPP міститься в перетині RP і co-RP. Нехай є машина Тьюринга типу Лас-Вегас C, яка вирішує задачу. Можна побудувати наступний RP алгоритм:

  • Запустимо C протягом принаймні подвоєного очікуваного часу роботи. Якщо отримана відповідь - повертаємо його. Якщо до моменту останову ніякої відповіді не отримано, говоримо "Ні".

Імовірність того, що буде отримано відповідь до моменту останову, дорівнює (з нерівності Маркова). Це в свою чергу означає, що ймовірність відповісти "Ні", коли насправді відповідь "Так", за рахунок останова, дорівнює , що задовольняє визначенню RP. Для доказу включення ZPP в co-RP можна або скористатися тим же міркуванням, або зауважити, що ZPP замкнутий щодо взяття доповнення.

Вважається легкими P L NL AC NC P-complete BQP BPP RP ZPP
Предпологаются складними NP ( co-NP NP-Complete Co-NP-complete) UP # P (# P-complete) IP PSPACE (PSPACE-complete) R PP AM
Вважається складними EXPTIME NEXPTIME EXPSPACE 2-EXPTIME PR RE Co-RE RE-complete Co-RE-complete PH
Список алгоритмів