Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение [ править ]

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

Отношение к другим классам сложности [ править ]

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

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

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

Ссылки [ править ]

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