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 через недетерминированные машины Тьюринга, где решение принимается при наличии хотя бы некоторой постоянной доли вычислительных путей. 

• Рекомендации и внешние ссылки

  • Статья содержит ссылки на дополнительные ресурсы и информацию о сложности вычислений.