- Класс 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» — нет.
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 Список алгоритмов Категория:- Классы сложности
Wikimedia Foundation. 2010.