В теорії обчислювальної складності, 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 замкнутий щодо взяття доповнення.