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