RL (сложность)
-
Определение рандомизированного логарифмического пространства (RL)
- RL — это класс задач, решаемых в логарифмическом пространстве за полиномиальное время с использованием вероятностных машин Тьюринга.
- RL отличается от RP, который не имеет ограничения по пространству.
-
Особенности вероятностных машин Тьюринга
- Вероятностные машины Тьюринга в RL никогда не принимают неверные решения, но могут ошибаться менее чем в 1/3 случаев.
- Ошибка может быть уменьшена до любого значения x с 0 < x < 1 за полиномиальное время.
-
Отношение к другим классам сложности
- RL иногда называют NL, так как он равен NL и содержит NL.
- RL содержится в BPL, который допускает двустороннюю ошибку.
- RL содержит L задач, решаемых детерминированными машинами Тьюринга в логарифмическом пространстве.
- Ноам Нисан показал, что RL содержится в SC, классе задач, решаемых за полиномиальное время в полилогарифмическом пространстве на детерминированных машинах Тьюринга.
-
Дерандомизация и эквивалентность классов сложности
- Считается, что RL равно L, что означает возможность полной дерандомизации логарифмических вычислений за полиномиальное время.
- Омер Рейнгольд доказал, что SL равно L, что является важным шагом в области безусловной дерандомизации.
Полный текст статьи: