Будемо вважати, що мову L належить класу RP ("randomized polynomial class" - випадковий поліноміальний), якщо він допускається ймовірнісної машиною Тьюринга M, для якої виконані наступні умови:

  • Якщо w не належить L, то ймовірність того, що M допускає w, дорівнює 0.
  • Якщо w належить L, то ймовірність того, що M допускає w, не ​​менше .
  • Існує поліном p (n), для якого, якщо w має довжину n, то обчислення M зупиняються після не більше p (n) кроків (незалежно від вмісту випадкової стрічки).

Примітка. Визначення класу RP використовує два поняття, які не пов'язані між собою:

  • У пунктах 1 і 2 визначається рандомізованих машина Тьюринга, яка називається машиною типу Монте-Карло.
  • У пункті 3 йдеться про час роботи, яке не залежить від того, чи є дана машина Тьюринга машиною типу Монте-Карло.

Примітка. Вибір в якості порогу в даному випадку не обов'язковий і дану константу можна замінити на іншу (0 < \ Epsilon <1). При цьому RP буде містити ті ж завдання, але мови, зумовлені конкретними рандомізованими машинами Тьюрінга, зміняться.


Суміжні класи складності

Якщо машина Тьюринга M відповідає "Так", то це гарантовано правда, в той час як "Ні" правда лише в деяких випадках. Клас складності co-RP визначається аналогічно, з тією лише різницею, що відповідь "Ні" є гарантованою правдою, а "Так" не завжди. Клас BPP описує алгоритми, які можуть дати неправильну відповідь в обох випадках. Клас, який є перетином RP і co-RP, називається ZPP.

Зв'язок з P і NP

Клас P є підмножиною класу RP, який, у свою чергу, є підмножиною класу NP. У тому числі, P є підмножиною Co-RP, що є підмножиною Co-NP. При цьому точно невідомо, чи є ці включення строгими. Більшість дослідників схиляється до версії, що PRP або RPNP, інакше P = NP (більшість вчених схиляється до того, що це неправда). Також невідомо RP = Co-RP, і чи є RP підмножиною перетину NP і Co-NP.

Яскравим прикладом задачі, яка лежить в Co-RP, але невідомо чи лежить вона в P є: визначити, чи є вираз з декількома цілими змінними тотожним нулем. Наприклад, "x * x - y * y - (x + y) * (xy)" тотожний нуль, в той час як "x * x + y * y" - немає.


Вважається легкими 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
Список алгоритмів