PL (сложность) - PL (complexity)

PL, или вероятностный L, - класс языков, распознаваемых рандомизированной машиной в логарифмическом пространстве за полиномиальное время с вероятностью>¹⁄₂ (это называется неограниченной ошибкой). Эквивалентно, как показано ниже, PL - это класс языков, распознаваемых рандомизированной машиной с неограниченным временем и неограниченным пространством журнала ошибок.

Примером полной проблемы PL (при сокращении лог-пространства) является определение того, является ли определитель матрицы (с целыми коэффициентами) положительным. Учитывая матрицу M и ряд п, тестирование с ${ displaystyle | M |> п}$^{[примечание 1]} также является PL полным. Напротив, проверка того, постоянный положительно PP полный.

PL^PL= PL в том смысле, что для каждого f из PL PL не изменяется, если его расширить, чтобы ${ Displaystyle х к е (А, х)}$ как подпрограмму, где A - входная строка.

PL содержит NL и BPL и содержится в NC₂.

Аппроксимирующий определитель в PL

Определитель интегральной матрицы можно свести к нахождению разницы между количеством принимающих и отклоняющих путей на ориентированном ациклическом графе полиномиального размера с выделенными узлами начала, принятия и отклонения.^[1]

Сравнение количества принимающих и отклоняющих путей можно выполнить в PL следующим образом. Измените граф, чтобы сделать все пути одинаковой длины и чтобы у каждого узла было не более двух преемников. Выбери случайный путь. Для каждого узла только с одним преемником с вероятностью неуспешно (выдача случайного ответа)¹⁄₂. В конце, принять, если мы достигли узла Принять, отклонить, если мы достигли узла отклонения, и потерпеть неудачу в противном случае. Каждый отдельный путь будет засчитан одинаково - хотя некоторые пути будут пройдены с большей вероятностью, это в точности компенсируется сниженной вероятностью продолжения по этому пути.

Вероятностный журнал без ограничения по времени

Если время не ограничено, машины могут работать в ожидаемом экспоненциальном времени - например, вести счетчик и увеличивать его с вероятностью.¹⁄₂ и обнулить в противном случае; остановка при переполнении счетчика. Если разрешена нулевая ошибка (или односторонняя ошибка), класс равен NL - машина может моделировать NL, пробуя случайные пути в течение экспоненциального количества времени и используя NL = coNL.

Если разрешена ограниченная ошибка, задача полного обещания или аппроксимации заключается в оценке стационарного распределения для эргодической Цепь Маркова. Не известно, что класс сложности равен PL, и попытка смоделировать PL через усиление вероятности черного ящика не удалась: несмотря на неограниченное время, машины с ограниченным журналом ошибок не могут отличить случайную монету от монеты, упавшей головой. ${ Displaystyle 1/2 + 1 / s (п)}$ того времени, когда ${ Displaystyle s (п)}$ растет суперполиномиально.

Для машин с неограниченным журналом ошибок неограниченное время может быть уменьшено до полиномиального следующим образом. Вычисление вероятности приемки может быть сведено к решению линейной системы. Для каждого штата я, добавьте переменную Икс_я - вероятность принятия, если текущее состояние равно i. Если нет пути от i до Принимать, набор Икс_я=0, и иначе выразить Икс_я в терминах состояний, непосредственно доступных из состояния i. Система может быть решена с использованием детерминантов и проверки того, ${ displaystyle | A |> 2 | B |}$ находится в PL.^{[примечание 1]} Одна из сложностей заключается в том, что коэффициенты находятся в NL (используя NL = coNL). Мы решаем эту проблему, угадывая «доказательство» для каждого значения коэффициента, ошибаясь, если предположение не работает, и гарантируя, что все пути делают одинаковое количество предположений для каждого коэффициента.

Примечания

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