Класс RP (Tlgvv RP)

Положение класса RP в иерархии классов сложности.

Будем считать, что язык 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. При этом точно неизвестно, являются ли эти включения строгими. Большинство исследователей склоняется к версии, что P ≠ RP или RP ≠ NP, иначе P = NP (большинство ученых склоняется к тому, что это неправда). Также неизвестно, верно ли, что RP = Co-RP, и является ли RP подмножеством пересечения NP и Co-NP.

Ярким примером задачи, которая лежит в Co-RP, но неизвестно лежит ли она в P является задача проверки двух многочленов на равенство: определить, является ли полиномиально выражение с несколькими целыми переменными тождественным нулем. Например, x · x − y · y − (x + y) · (x − y) — тождественный нуль, в то время как x · x + y · y — нет.