Войти
Случайное логарифмическое пространство (RL), иногда называемое RLP (Randomized Logarithmic -пространство Полиномиальное время), является классом сложности из задач теории сложности вычислений, решаемых в логарифмическом пространстве и полиномиальном времени с вероятностные машины Тьюринга с односторонней ошибкой. Он назван по аналогии с RP, который похож, но не имеет логарифмического ограничения по пространству.
Вероятностные машины Тьюринга в определении RL никогда не принимают ошибочно, но могут отклонять неправильно менее чем в 1/3 случаев; это называется односторонней ошибкой. Константа 1/3 произвольна; любой x с 0 < x < 1 would suffice. This error can be made 2 times smaller for any polynomial p(x) without using more than polynomial time or logarithmic space by running the algorithm repeatedly.
Иногда имя RL зарезервировано для класса задач, решаемых вероятностными машинами в логарифмическом пространстве за неограниченное время. Однако можно показать, что этот класс равен NL, используя вероятностный счетчик, и поэтому вместо него обычно упоминается как NL ; это также показывает, что RL содержится в NL. RLсодержится в BPL, что аналогично, но допускает двустороннюю ошибку (неправильные принятия). RL содержит L, проблемы, решаемые детерминированными машинами Тьюринга в пространстве журнала, поскольку его определение является просто более общим.
Ноам Нисан показал в 1992 году слабый результат дерандомизации, согласно которому RL содержится в SC, классе задач, разрешимых за полиномиальное время и полилогарифмическое пространство на детерминированном Машина Тьюринга; другими словами, в полилогарифмическом пространстве детерминированная машина может моделировать вероятностные алгоритмы логарифмического пространства.
Предполагается, что RL равно L, то есть, что вычисление лог-пространства с полиномиальным временем может быть полностью дерандомизировано; основные доказательства этого были представлены Reingold et al. в 2005 году. Доказательство тому - святой Грааль усилий в области безусловной дерандомизации классов сложности. Большим шагом вперед стало доказательство Омера Рейнгольда, что SL равно L.
