Оглавление
RP (сложность)
-
Определение рандомизированного полиномиального времени (RP)
- RP – это класс задач, решаемых вероятностной машиной Тьюринга за полиномиальное время.
- Алгоритм всегда возвращает “НЕТ”, если правильный ответ “НЕТ”, и “ДА” с вероятностью не менее 1/2.
- Если алгоритм возвращает “ДА”, то это означает, что правильный ответ “ДА”.
- Если алгоритм возвращает “НЕТ”, это не обязательно означает, что правильный ответ “НЕТ”.
-
Практическое применение и вероятность ошибок
- Алгоритмы в RP очень практичны, если доступен источник случайных чисел.
- Вероятность ошибки при многократном запуске алгоритма ниже, чем вероятность повреждения памяти компьютера.
- Вероятность ошибки может быть заменена на любую ненулевую константу, не зависящую от входных данных.
-
Формальное определение RP
- Язык L находится в RP, если существует вероятностная машина Тьюринга M, которая выполняется за полиномиальное время и выдает 1 с вероятностью не менее 1/2 для всех x в L.
- Язык L находится в RP, если существует детерминированная машина Тьюринга M и многочлен p, которые выполняются за полиномиальное время p и выдают 1 с вероятностью не менее 1/2 для всех x в L и 0 для всех x, не входящих в L.
-
Связанные классы сложности
- co-RP – это дополнение к RP, где ответ “ДА” может быть неправильным.
- BPP – это класс алгоритмов, которые могут давать неправильные ответы в обоих случаях “ДА” и “НЕТ”.
- ZPP – это пересечение RP и co-RP.
- Некоторые авторы используют название co-R вместо co-RP.
-
Связь с P и NP
- RP является подмножеством P и NP.
- Неизвестно, являются ли эти включения строгими.
- Если P = BPP, то RP, co-RP и P разрушаются.
- Если P ∈ NP, то RP строго содержится в NP.
- Неясно, является ли RP = co-RP или RP является подмножеством пересечения NP и co-NP.
-
Примеры задач в RP
- Проверка полиномиальной идентичности – пример задачи в co-RP, которая не известна как задача в P.
- Альтернативное определение RP через недетерминированные машины Тьюринга, где решение принимается при наличии хотя бы некоторой постоянной доли вычислительных путей.
-
Рекомендации и внешние ссылки
- Статья содержит ссылки на дополнительные ресурсы и информацию о сложности вычислений.
Полный текст статьи: