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

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

Примером полной задачи PL (при уменьшении лог-пространства) является определение того, является ли определитель матрицы (с целыми коэффициентами) положительным. Учитывая матрицу M и число n , тестирование с помощью $|M|>n$ также является PL-полным. Напротив, проверка того, является ли перманент матрицы положительной, является завершенной PP .

ПЛ ^ПЛ =PL в том смысле, что для каждого f в PL PL не меняется, если его расширить, чтобы допустить ⁠ $x\to f(A,x)$⁠ как подпрограмма, где A — входная строка.

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

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

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

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

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

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

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

Для машин с неограниченным пространством журнала ошибок неограниченное время можно сократить до полиномиального времени следующим образом. Вычисление вероятности принятия можно свести к решению линейной системы. Для каждого состояния i добавьте переменную x _i — вероятность принятия, если текущее состояние равно i. нет Если пути от i до Accept , установите x _i =0 и в противном случае выразите x _i через состояния, непосредственно достижимые из состояния i. Систему можно решить, используя определители и проверяя, $|A|>2|B|$ находится в ПЛ. Одна из сложностей заключается в том, что коэффициенты находятся в NL (при использовании NL=coNL). Мы решаем эту проблему, угадывая «доказательство» для каждого значения коэффициента, теряя неудачу, если предположение не работает, и гарантируя, что все пути делают одинаковое количество предположений для каждого коэффициента.