РП (сложность)
В сложности вычислений теории рандомизированное полиномиальное время ( 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 |
- Он всегда работает за полиномиальное время по входному размеру.
- Если правильный ответ НЕТ, он всегда возвращает НЕТ.
- Если правильный ответ ДА, то он возвращает ДА с вероятностью не менее 1/2 (в противном случае он возвращает НЕТ).
Другими словами, алгоритму разрешено подбрасывать действительно случайную монету во время его работы. Единственный случай, когда алгоритм может вернуть YES, — это если фактический ответ — YES; следовательно, если алгоритм завершается и выдает ДА, то правильный ответ определенно ДА; однако алгоритм может завершиться с ответом НЕТ независимо от фактического ответа. То есть, если алгоритм возвращает НЕТ, это может быть неправильно.
Некоторые авторы называют этот класс R , хотя это имя чаще используется для класса рекурсивных языков .
Если правильный ответ — ДА и алгоритм запускается n раз, причем результат каждого запуска статистически независим от других, то он вернет ДА хотя бы один раз с вероятностью не менее 1–2. − п . Таким образом, если алгоритм запускается 100 раз, то вероятность того, что он каждый раз даст неправильный ответ, ниже, чем вероятность того, что космические лучи повредят память компьютера, на котором работает алгоритм. [1] В этом смысле, если доступен источник случайных чисел, большинство алгоритмов RP весьма практичны.
Дробь 1/2 в определении произвольна. Набор RP будет содержать точно такие же задачи, даже если 1/2 заменить любой постоянной ненулевой вероятностью меньше 1; здесь константа означает независимость от входных данных алгоритма.
Формальное определение
[ редактировать ]Язык L находится в RP тогда и только тогда, когда существует вероятностная машина Тьюринга M такая, что
- M работает в течение полиномиального времени на всех входах
- Для всех x в L выводит 1 с вероятностью , M большей или равной 1/2.
- Для всех x, не входящих в L , M выводит 0
Альтернативно, RP можно определить, используя только детерминированные машины Тьюринга. Язык L находится в RP тогда и только тогда, когда существуют полином p и детерминированная машина Тьюринга M такие, что
- M работает в течение полиномиального времени p на всех входах
- Для всех x в L доля строк y длины p (| x |), удовлетворяющих больше или равно 1/2
- Для всех x не из L и всех строк y длины p (| x |),
В этом определении строка y соответствует результату случайных подбрасываний монеты, которые могла бы произвести вероятностная машина Тьюринга. Для некоторых приложений это определение предпочтительнее, поскольку в нем не упоминаются вероятностные машины Тьюринга.
Связанные классы сложности
[ редактировать ]
Определение RP гласит, что ответ ДА всегда правильный, а ответ НЕТ может быть неправильным, поскольку экземпляр ДА может возвращать ответ НЕТ. класса сложности Со-RP является дополнением, где ответ ДА может быть неправильным, а ответ НЕТ всегда верен.
Класс BPP описывает алгоритмы, которые могут давать неправильные ответы как в экземплярах YES, так и NO, и, таким образом, содержит как RP , так и co-RP . Пересечение множеств RP и ко-RP называется ZPP . Так же, как RP может называться R , некоторые авторы используют название co-R, а не co-RP .
Подключение к P и NP
[ редактировать ]
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 .
Естественным примером проблемы в совместном RP, о которой в настоящее время не известно, в P является проверка полиномиальной идентичности , проблема определения того, является ли данное многомерное арифметическое выражение над целыми числами нулевым полиномом. Например, x · x - y · y - ( x + y ) · ( x - y ) является нулевым полиномом, а x · x + y · y нет.
Альтернативная характеристика RP , которую иногда проще использовать, - это набор проблем, распознаваемых недетерминированными машинами Тьюринга , где машина принимает, если и только если принимается хотя бы некоторая постоянная часть вычислительных путей, независимая от размера входных данных. С другой стороны, NP нужен только один принимающий путь, который может составлять экспоненциально малую часть путей. Эта характеристика делает очевидным тот факт, что RP является подмножеством NP .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Это сравнение приписывается Майклу О. Рабину на стр. 252 из Гасарч, Уильям (2014), «Классификация проблем по классам сложности», в книге Мемон, Атиф (ред.), « Достижения в области компьютеров», Vol. 95 (PDF) , Academic Press, стр. 239–292 .
 | Эта статья нуждается в дополнительных цитатах для проверки . ( октябрь 2014 г. ) |