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

Рандомизированное логарифмическое пространство (RL),[1] иногда называют RLP (Рандомизированное полиномиальное время в логарифмическом пространстве),[2] это класс сложности из теория сложности вычислений проблемы, решаемые в логарифмическое пространство и полиномиальное время с вероятностные машины Тьюринга с односторонняя ошибка. Назван по аналогии с RP, который аналогичен, но не имеет ограничения на логарифмический размер.

Определение

Вероятностные машины Тьюринга в определении RL никогда не принимайте неправильно, но им разрешается ошибочно отклонять менее 1/3 случаев; это называется односторонняя ошибка. Константа 1/3 произвольна; любой Икс с 0 < Икс <1 будет достаточно. Эту ошибку можно сделать 2−п(Икс) раз меньше для любого полинома п(Икс) без использования более чем полиномиального времени или логарифмического пространства путем многократного выполнения алгоритма.

Отношение к другим классам сложности

Иногда имя RL зарезервирован для класса задач, решаемых вероятностными машинами в логарифмическом пространстве в неограниченный время. Однако можно показать, что этот класс равен NL с использованием вероятностного счетчика, поэтому его обычно называют NL вместо; это также показывает, что RL содержится в NL. RL содержится в BPL, что аналогично, но допускает двустороннюю ошибку (неверно принимает). RL содержит L, проблемы, решаемые детерминированные машины Тьюринга в пространстве журнала, поскольку его определение является просто более общим.

Ноам Нисан показал в 1992 г. слабые дерандомизация результат, что RL содержится в SC,[3] класс задач, решаемых за полиномиальное время и в полилогарифмическом пространстве на детерминированной машине Тьюринга; другими словами, учитывая полилогарифмический пространство, детерминированная машина может моделировать логарифмический космические вероятностные алгоритмы.

Верят что RL равно L, то есть это вычисление лог-пространства за полиномиальное время может быть полностью дерандомизировано; основные доказательства этого были представлены Reingold et al. в 2005 году.[4] Доказательство этого - святой Грааль усилий в области безусловной дерандомизации классов сложности. Важным шагом вперед стало доказательство Омера Рейнгольда, что SL равно L.

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

  1. ^ Зоопарк сложности: RL
  2. ^ Бородин А., Кук С. Даймонд, W.L. Руццо и М. Томпа. Два применения индуктивного счета для задач дополнения. SIAM Journal on Computing, 18 (3): 559–578. 1989 г.
  3. ^ Нисан, Ноам (1992), "RL ⊆ SC", Материалы 24-го симпозиума ACM по теории вычислений (STOC '92), Виктория, Британская Колумбия, Канада, стр. 619–623, Дои:10.1145/129712.129772.
  4. ^ О. Рейнгольд и Л. Тревизан и С. Вадхан. Псевдослучайные блуждания в бирегулярных графах и проблема RL vs.L, ECCC  TR05-022, 2004.