БПЛ (сложность)

В сложности вычислений теории BPL (вероятностное логарифмическое пространство с ограниченной ошибкой), иногда называемый BPLP (вероятностно-логарифмическое полиномиальное время с ограниченной ошибкой), — класс сложности задач, решаемых в логарифмическом пространстве и за полиномиальное время с помощью вероятностных машин Тьюринга с двусторонней ошибкой . Он назван по аналогии с BPP , который похож, но не имеет ограничений в логарифмическом пространстве.

Модель ошибки

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

Связанные классы

Поскольку двусторонняя ошибка является более общей, чем односторонняя ошибка, RL и его дополнительный со-RL содержатся в BPL . BPL также содержится в PL , который аналогичен, за исключением того, что граница ошибки равна 1/2, а не константе меньше 1/2; как и класс PP , класс PL менее практичен, поскольку может потребоваться большое количество раундов, чтобы уменьшить вероятность ошибки до небольшой константы.

Нисан (1994) показал слабый дерандомизации результат , заключающийся в том, что BPL содержится в SC . SC — класс задач, решаемых за полиномиальное время и полилогарифмическое пространство на детерминированной машине Тьюринга; другими словами, этот результат показывает, что при наличии полилогарифмического пространства детерминированная машина может моделировать в логарифмическом вероятностные алгоритмы пространстве.

BPL содержится в NC и в L/poly . Сакс и Чжоу показали, что BPL содержится в DSPACE (журнал ^3/2 н), а в 2021 году Хоза улучшил это, чтобы показать, что BPL содержится в DSPACE. $(\log ^{3/2}(n)/{\sqrt {\log \log n}})$.