Войти
В теории сложности вычислений, рандомизированное полиномиальное время (RP) - это класс сложности задач, для которых существует вероятностная машина Тьюринга со следующими свойствами:
| алгоритм RP (1 запуск) | ||
|---|---|---|
| Получен ответ Правильный. ответ | Да | Нет |
| Да | ≥ 1/2 | ≤ 1/2 |
| Нет | 0 | 1 |
| Алгоритм RP (n запусков) | ||
| Получен ответ Правильный. ответ | Да | Нет |
| Да | ≥ 1-2 | ≤ 2 |
| Нет | 0 | 1 |
| алгоритм co-RP (1 запуск) | ||
| Получен ответ Правильный. ответ | Да | Нет |
| Да | 1 | 0 |
| Нет | ≤ 1/2 | ≥ 1/2 |
В других случаях Другими словами, алгоритм может подбрасывать действительно случайную монету во время ее работы. Единственный случай, когда алгоритм может вернуть ДА, - это если фактический ответ ДА; поэтому, если алгоритм завершается и выдает ДА, то правильный ответ определенно ДА; однако алгоритм может завершиться ответом «НЕТ» независимо от фактического ответа. То есть, если алгоритм вернет НЕТ, это может быть неправильно.
Некоторые авторы называют этот класс R, хотя это имя чаще используется для класса рекурсивных языков.
Если правильный ответ - ДА и алгоритм выполняется n раз с результатом каждого запуска статистически независимым от остальных, то он вернет ДА хотя бы один раз с вероятностью не менее 1-2. Таким образом, если алгоритм выполняется 100 раз, то вероятность того, что он даст неправильный ответ каждый раз ниже, чем вероятность того, что космические лучи испортили память компьютера, на котором запущен алгоритм. В этом смысле, если доступен источник случайных чисел, большинство алгоритмов в RP очень практично.
Дробь 1/2 в определении произвольная. Набор RP будет содержать точно такие же проблемы, даже если 1/2 будет заменена любой постоянной ненулевой вероятностью меньше 1; здесь константа означает независимость от входа в алгоритм.
Язык L находится в RP тогда и только тогда, когда существует вероятностная машина Тьюринга M, такая, что
В качестве альтернативы RP может быть определен с использованием только детерминированных машин Тьюринга. Язык L находится в RP тогда и только тогда, когда существует полином p и детерминированная машина Тьюринга M, так что
, больше или равно ⁄ 2
В этом определении строка y соответствует результату случайных подбрасываний монеты, которые могла бы сделать вероятностная машина Тьюринга. Для некоторых приложений это определение предпочтительнее, поскольку в нем не упоминаются вероятностные машины Тьюринга.
RP по отношению к другим классам вероятностной сложности (ZPP, co-RP, BPP, BQP, PP ), которые обобщают P в пределах PSPACE. Неизвестно, являются ли какие-либо из этих ограничений строгими. Определение RP гласит, что ответ ДА всегда правильный, а ответ НЕТ может быть неправильным (поскольку вопрос с ответом ДА может быть иногда отвечал НЕТ). Другими словами, хотя на НЕТ вопросы всегда отвечают НЕТ, вы не можете доверять ответу НЕТ, это может быть ошибочный ответ на вопрос ДА. Класс сложности co-RP определяется аналогично, за исключением того, что НЕТ всегда правильно, а ДА может быть неправильным. Другими словами, он принимает все экземпляры YES, но может либо принимать, либо отклонять экземпляры NO. Класс 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, которую иногда проще использовать, - это набор проблем, распознаваемых недетерминированными машинами Тьюринга, где машина принимает тогда и только тогда, когда хотя бы некоторые постоянная доля путей вычисления, независимо от размера ввода, accept. NP, с другой стороны, требуется только один путь приема, который может составлять экспоненциально малую часть путей. Эта характеристика делает очевидным тот факт, что RP является подмножеством NP .
