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