Класс 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» — нет.

Классы сложности алгоритмов

 

Cчитаются лёгкими	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
Cчитаются сложными	EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH
Список алгоритмов