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

В теория сложности вычислений, рандомизированное полиномиальное время (RP) это класс сложности проблем, для которых вероятностная машина Тьюринга существует с этими свойствами:

Алгоритм RP (1 запуск)
Ответ произведен
Правильный
отвечать
даНет
да≥ 1/2≤ 1/2
Нет01
Алгоритм RP (п работает)
Ответ произведен
Правильный
отвечать
даНет
да≥ 1 − 2−п≤ 2−п
Нет01
алгоритм co-RP (1 запуск)
Ответ произведен
Правильный
отвечать
даНет
да10
Нет≤ 1/2≥ 1/2
  • Он всегда выполняется за полиномиальное время в размере ввода
  • Если правильный ответ НЕТ, всегда возвращается НЕТ.
  • Если правильный ответ - ДА, то он возвращает ДА ​​с вероятностью не менее 1/2 (в противном случае возвращается НЕТ).

Другими словами, алгоритм позволяет подбросить действительно случайную монету во время ее движения. Единственный случай, когда алгоритм может вернуть ДА, - это если фактический ответ ДА; следовательно, если алгоритм завершается и выдает ДА, то правильный ответ определенно ДА; однако алгоритм может завершиться с NO несмотря на фактического ответа. То есть, если алгоритм вернет НЕТ, это может быть неправильно.

Некоторые авторы называют этот класс р, хотя это имя чаще используется для класса рекурсивные языки.

Если правильный ответ ДА ​​и алгоритм запущен п раз с результатом каждого запуска статистически независимый остальных, то он вернет YES хотя бы один раз с вероятностью не менее 1 − 2−п. Таким образом, если алгоритм запускается 100 раз, то вероятность того, что он каждый раз будет давать неправильный ответ, ниже, чем вероятность того, что космические лучи испортили память компьютера, на котором запущен алгоритм.[1] В этом смысле, если доступен источник случайных чисел, большинство алгоритмов в RP очень практичны.

Дробь 1/2 в определении произвольна. Набор RP будет содержать точно такие же проблемы, даже если 1/2 заменяется любой постоянной ненулевой вероятностью меньше 1; здесь константа означает независимость от входа в алгоритм.

Формальное определение

Язык L в RP тогда и только тогда, когда существует вероятностная машина Тьюринга M, так что

  • M работает за полиномиальное время на всех входах
  • Для всех Икс в L, M выводит 1 с вероятностью больше или равной1⁄2
  • Для всех Икс не в L, M выходы 0

В качестве альтернативы, RP могут быть определены с использованием только детерминированных машин Тьюринга. Язык L в RP тогда и только тогда, когда существует многочлен п и детерминированная машина Тьюринга M, так что

  • M работает за полиномиальное время на всех входах
  • Для всех Икс в L, доля строк у длины п(|Икс|), которые удовлетворяют больше или равно1⁄2
  • Для всех Икс не в L, и все струны у длины п(|Икс|),

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

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

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

Определение RP говорит, что ответ ДА ​​всегда правильный, а ответ НЕТ может быть неправильным (потому что на вопрос с ответом ДА иногда можно ответить НЕТ). Другими словами, хотя на НЕТ вопросы всегда отвечают НЕТ, вы не можете доверять ответу НЕТ, это может быть ошибочный ответ на вопрос ДА. Класс сложности co-RP определяется аналогично, за исключением того, что НЕТ всегда правильно, а ДА может быть неправильным. Другими словами, он принимает все экземпляры YES, но может либо принимать, либо отклонять экземпляры NO. Класс BPP описывает алгоритмы, которые могут давать неправильные ответы как на ДА, так и на НЕТ, и, таким образом, содержит оба RP и co-RP. Пересечение множеств RP и co-RP называется ЗПП. Как только RP можно назвать р, некоторые авторы используют имя co-R скорее, чем co-RP.

Подключение к П и НП

Вопрос, Web Fundamentals.svgНерешенная проблема в информатике:
(больше нерешенных проблем в информатике)

п это подмножество RP, который является подмножеством НП. По аналогии, п это подмножество co-RP который является подмножеством со-НП. Неизвестно, являются ли эти включения строгими. Однако если общепринятая гипотеза п = BPP верно, тогда RP, co-RP, и п коллапс (все равны). Предполагая дополнительно, что п ≠ НП, отсюда следует, что RP строго содержится в НП. Неизвестно, были ли RP = co-RP, или будь RP является подмножеством пересечения НП и со-НП, хотя это подразумевает п = BPP.

Естественный пример проблемы в co-RP в настоящее время не известно, чтобы быть в п является Проверка полиномиальной идентичности, проблема определения, является ли данное многомерное арифметическое выражение над целыми числами полиномом нуля. Например, Икс·Икс − у·у − (Икс + у)·(Икс − у) является нулевым полиномом, аИкс·Икс + у·у не является.

Альтернативная характеристика RP что иногда легче использовать, это набор проблем, распознаваемых недетерминированные машины Тьюринга где машина принимает, если и только если принимает хотя бы некоторую постоянную часть путей вычисления, независимо от размера ввода. НП с другой стороны, требуется только один путь приема, который может составлять экспоненциально малую часть путей. Эта характеристика делает тот факт, что RP это подмножество НП очевидный.

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

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

  1. ^ Это сравнение приписывается Майкл О. Рабин на стр. 252 из Гасарх, Уильям (2014), «Классификация проблем по классам сложности», в Memon, Atif (ed.), Достижения в области компьютеров, Vol. 95 (PDF), Academic Press, стр. 239–292..

внешняя ссылка