В теории сложности вычислений рандомизированное полиномиальное время ( РП ) — это класс сложности задач, для которых существует вероятностная машина Тьюринга со следующими свойствами:
Другими словами, алгоритму разрешено подбрасывать действительно случайную монету во время его работы. Единственный случай, когда алгоритм может вернуть ДА, это если фактический ответ ДА; поэтому, если алгоритм завершается и выдает ДА, то правильный ответ определенно ДА; однако алгоритм может завершиться с НЕТ независимо от фактического ответа. То есть, если алгоритм возвращает НЕТ, он может быть неверным.
Некоторые авторы называют этот класс R , хотя это название чаще используется для класса рекурсивных языков .
Если правильный ответ — ДА, и алгоритм запускается n раз, и результат каждого запуска статистически независим от других, то он вернет ДА по крайней мере один раз с вероятностью по крайней мере 1 − 2 − n . Таким образом, если алгоритм запускается 100 раз, то вероятность того, что он каждый раз даст неправильный ответ, ниже, чем вероятность того, что космические лучи повредят память компьютера, на котором запущен алгоритм. [1] В этом смысле, если доступен источник случайных чисел, большинство алгоритмов в RP весьма практичны.
Дробь 1/2 в определении произвольна. Набор RP будет содержать точно такие же проблемы, даже если 1/2 заменить любой константой с ненулевой вероятностью, меньшей 1; здесь константа означает независимость от входных данных алгоритма.
Язык L принадлежит RP тогда и только тогда, когда существует вероятностная машина Тьюринга M , такая что
В качестве альтернативы RP можно определить, используя только детерминированные машины Тьюринга. Язык L находится в RP тогда и только тогда, когда существует полином p и детерминированная машина Тьюринга M , такие, что
В этом определении строка y соответствует выходу случайных подбрасываний монеты, которые могла бы сделать вероятностная машина Тьюринга. Для некоторых приложений это определение предпочтительнее, поскольку оно не упоминает вероятностные машины Тьюринга.
Определение RP гласит, что ответ ДА всегда правильный, а ответ НЕТ может быть неправильным, поскольку экземпляр ДА может вернуть ответ НЕТ. Класс сложности co-RP является дополнением, где ответ ДА может быть неправильным, а ответ НЕТ всегда правильный.
Класс BPP описывает алгоритмы, которые могут давать неверные ответы как на ДА, так и на НЕТ, и, таким образом, содержит как RP , так и co-RP . Пересечение множеств RP и co-RP называется ZPP . Так же, как RP может называться R , некоторые авторы используют название co-R вместо co-RP .
P является подмножеством RP , которое является подмножеством NP . Аналогично, P является подмножеством co-RP , которое является подмножеством co-NP . Неизвестно, являются ли эти включения строгими. Однако, если общепринятая гипотеза P = BPP верна, то RP , co-RP и P разрушаются (все равны). Если дополнительно предположить, что P ≠ NP , то это означает, что RP строго содержится в NP . Неизвестно, является ли RP = co-RP , или является ли RP подмножеством пересечения NP и co-NP , хотя это подразумевалось бы из P = BPP .
Естественным примером проблемы в co-RP, которая в настоящее время не известна как проблема в P, является проверка идентичности полиномов , проблема определения, является ли заданное многомерное арифметическое выражение над целыми числами нулевым полиномом. Например, x · x − y · y − ( x + y )·( x − y ) является нулевым полиномом, а x · x + y · y — нет.
Альтернативная характеристика RP , которая иногда проще в использовании, — это набор проблем, распознаваемых недетерминированными машинами Тьюринга , где машина принимает тогда и только тогда, когда принимает по крайней мере некоторая постоянная доля путей вычисления, независимо от размера входных данных. NP , с другой стороны, нуждается только в одном принимающем пути, который может составлять экспоненциально малую долю путей. Эта характеристика делает очевидным тот факт, что RP является подмножеством NP .
