РЛ (сложность)
Рандомизированное логарифмическое пространство ( RL ), [1] иногда называемый RLP (рандомизированный логарифмический полином-время), [2] — сложности класс задач теории сложности вычислений, решаемых в логарифмическом пространстве и полиномиальном времени с помощью вероятностных машин Тьюринга с односторонней ошибкой . Он назван по аналогии с RP , который похож, но не имеет логарифмического ограничения по пространству.
Определение
[ редактировать ]Вероятностные машины Тьюринга в определении RL никогда не принимают неправильно, но допускают ошибочное отклонение менее чем в 1/3 случаев; это называется односторонняя ошибка . Константа 1/3 произвольна; любого x с 0 < x < 1 будет достаточно. Эту ошибку можно допустить 2 - п ( Икс ) раз меньше для любого полинома p ( x ) без использования более чем полиномиального времени или логарифмического пространства путем многократного запуска алгоритма.
Связь с другими классами сложности
[ редактировать ]Иногда название RL зарезервировано для класса задач, решаемых вероятностными машинами в логарифмическом пространстве за неограниченное время. Однако с помощью вероятностного счетчика можно показать, что этот класс равен NL , поэтому вместо этого его обычно называют NL ; это также показывает, что RL содержится в NL . RL содержится в BPL , который аналогичен, но допускает двустороннюю ошибку (неверное принятие). RL содержит L — проблемы, решаемые детерминированными машинами Тьюринга в журнальном пространстве, поскольку его определение является более общим.
Ноам Нисан показал в 1992 году слабый дерандомизации результат , заключающийся в том, что RL содержится в SC , [3] класс задач, решаемых за полиномиальное время и полилогарифмическое пространство на детерминированной машине Тьюринга; другими словами, при наличии полилогарифмического пространства детерминированная машина может моделировать логарифмического вероятностные алгоритмы пространства.
Считается, что RL равно L , то есть вычисление лог-пространства за полиномиальное время может быть полностью дерандомизировано; основные доказательства этого были представлены Reingold et al. в 2005 году. [4] Доказательством этого является Святой Грааль усилий в области безусловной дерандомизации классов сложности. Важным шагом вперед стало доказательство Омера Рейнгольда того, SL равен L. что
Ссылки
[ редактировать ]- ^ Зоопарк сложности : RL
- ^ А. Бородин, С.А. Кук, П.В. Даймонд, В.Л. Руццо и М. Томпа. Два применения индуктивного счета для задач дополнения. SIAM Journal on Computing, 18(3):559–578. 1989.
- ^ Нисан, Ноам (1992), «RL ⊆ SC», Труды 24-го симпозиума ACM по теории вычислений (STOC '92) , Виктория, Британская Колумбия, Канада, стр. 619–623, doi : 10.1145/129712.129772
{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) . - ^ О. Рейнгольд, Л. Тревизан и С. Вадхан. Псевдослучайные блуждания в бирегулярных графах и проблема RL и L, ECCC TR05-022 , 2004.