РП (сложность) - RP (complexity)

В теории сложности вычислений , рандомизированное полиномиальное время ( 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 раз, то вероятность того, что он каждый раз будет давать неправильный ответ, ниже, чем вероятность того, что космические лучи испортили память компьютера, на котором запущен алгоритм. В этом смысле, если доступен источник случайных чисел, большинство алгоритмов в 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 работает за полиномиальное время на всех входах
  • Для всех x в L доля строк y длины p (| x |), которые удовлетворяют , больше или равна 1/2
  • Для всех x, не принадлежащих L , и всех строк y длины p (| x |),

В этом определении строка y соответствует результату случайных подбрасываний монеты, которые могла бы сделать вероятностная машина Тьюринга. Для некоторых приложений это определение предпочтительнее, поскольку в нем не упоминаются вероятностные машины Тьюринга.

Связанные классы сложности

Схема рандомизированных классов сложности
RP по отношению к другим классам вероятностной сложности ( ZPP , co-RP, BPP , BQP , PP ), которые обобщают P в рамках PSPACE . Неизвестно, являются ли какие-либо из этих условий строгими.

Определение 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 коллапсируют (все равны). Предполагая дополнительно, что PNP , это означает, что 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 .

Смотрите также

Рекомендации

Внешние ссылки