Клас ZPP

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