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

В теория сложности вычислений, BPL (Вероятностное логарифмическое пространство с ограниченной ошибкой),[1] иногда называют BPLP (Полиномиальное время вероятностного логарифмического пространства с ограниченной ошибкой),[2] это класс сложности проблем, решаемых в логарифмическое пространство и полиномиальное время с вероятностные машины Тьюринга с двусторонняя ошибка. Назван по аналогии с BPP, который аналогичен, но не имеет ограничения на логарифмический размер.

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

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

Родственные классы

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

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

BPL содержится в NC И в DSPACE(бревно3/2 п) [4] И в L / поли.

Рекомендации

  1. ^ «Зоопарк сложности: БПЛ». Архивировано из оригинал на 2012-08-05. Получено 2011-10-04.
  2. ^ Бородин, А.; Кук, С.А.; Dymond, P.W .; Ruzzo, W. L .; Томпа, М. (1989), "Два применения индуктивного счета для задач дополнения", SIAM Журнал по вычислениям, 18 (3): 559–578, CiteSeerX  10.1.1.394.1662, Дои:10.1137/0218038
  3. ^ Нисан, Н. (1994), "RL ⊆ SC", Вычислительная сложность, 4 (1): 1–11, Дои:10.1007 / BF01205052, Более ранняя версия этой статьи появилась на конференции 1992 г. Симпозиум по теории вычислений
  4. ^ Конспект лекций по теории сложности