Введение

Случайное логарифмическое пространство (RL), иногда называемое RLP (случайное логарифмическое пространство полиномиального времени), — это класс сложности задач теории вычислительной сложности, разрешимых в логарифмическом пространстве и за полиномиальное время с помощью вероятностных машин Тьюринга с односторонней ошибкой. Он назван по аналогии с 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 году доказал слабый результат дерандомизации, что RL содержится в SC, классе задач, разрешимых за полиномиальное время и полилогарифмическое пространство на детерминированной машине Тьюринга; другими словами, при наличии полилогарифмического пространства детерминированная машина может эмулировать вероятностные алгоритмы с логарифмическим объемом памяти. Предполагается, что RL равен L, то есть вычисления за полиномиальное время с использованием логарифмического объема памяти могут быть полностью дерандомизированы; существенные доказательства этого были представлены Рейнгольдом и др. в 2005 году. Доказательство этого является главной целью усилий в области безусловной дерандомизации классов сложности. Важным шагом вперед стало доказательство Омера Рейнгольда, что SL равен L.