NL (сложность)

Нерешенная проблема в информатике :

⁠ ⁠${\displaystyle {\mathsf {L{\overset {?}{=}}NL}}}$

(еще нерешенные проблемы в информатике)

В теории сложности вычислений NL ( недетерминированное логарифмическое пространство) — это класс сложности, содержащий задачи принятия решений , которые могут быть решены недетерминированной машиной Тьюринга с использованием логарифмического объема памяти .

NL является обобщением L , класса для задач логпространства на детерминированной машине Тьюринга . Поскольку любая детерминированная машина Тьюринга является также недетерминированной машиной Тьюринга , мы имеем, что L содержится в NL .

NL можно формально определить в терминах недетерминированного пространства вычислительных ресурсов (или NSPACE) как NL = NSPACE (log n ).

Важные результаты в теории сложности позволяют нам связать этот класс сложности с другими классами, говоря нам об относительной мощности задействованных ресурсов. Результаты в области алгоритмов , с другой стороны, говорят нам, какие проблемы можно решить с помощью этого ресурса. Как и многое в теории сложности, многие важные вопросы о NL все еще остаются открытыми (см. Нерешенные проблемы в информатике ).

Иногда NL называют RL из-за его вероятностного определения, приведенного ниже; однако это название чаще используется для обозначения рандомизированного логарифмического пространства , которое, как известно, не равно NL .

Известно, что несколько задач являются NL-полными при сокращениях логарифмического пространства , включая ST-связность и 2-выполнимость . ST-связность спрашивает, для узлов S и T в направленном графе , достижимо ли T из S. 2 - выполнимость спрашивает, если задана пропозициональная формула, каждое предложение которой является дизъюнкцией двух литералов, существует ли назначение переменной, делающее формулу истинной. Примером экземпляра , где указывает не , может быть:${\displaystyle \отрицательный}$

${\displaystyle (x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})}$

Известно, что NL содержится в P , поскольку существует полиномиальный алгоритм для 2-выполнимости , но неизвестно, NL = P или L = NL . Известно, что NL = co-NL , где co-NL — класс языков, дополнения которых находятся в NL . Этот результат ( теорема Иммермана–Селепеценьи ) был независимо обнаружен Нилом Иммерманом и Робертом Селепеценьи в 1987 году; за эту работу они получили премию Гёделя 1995 года.

В сложности схемы NL можно поместить в иерархию NC . В Papadimitriou 1994, теорема 16.1, мы имеем:

${\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}$.

Точнее, NL содержится в AC ¹ . Известно, что NL равен ZPL , классу задач, решаемых рандомизированными алгоритмами в логарифмическом пространстве и неограниченном времени без ошибок. Однако неизвестно и не считается, что он равен RLP или ZPLP , ограничениям RL и ZPL по полиномиальному времени , которые некоторые авторы называют RL и ZPL .

Мы можем связать NL с детерминированным пространством, используя теорему Сэвича , которая говорит нам, что любой недетерминированный алгоритм может быть смоделирован детерминированной машиной в не более чем квадратично большем пространстве. Из теоремы Сэвича мы имеем непосредственно, что:

${\displaystyle {\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{эквивалентно, }}{\mathsf {NL\subseteq L}}^{2}.}$

Это было самое сильное включение детерминированного пространства, известное в 1994 году (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Поскольку более крупные классы пространств не подвержены влиянию квадратичных увеличений, недетерминированные и детерминированные классы считаются равными, так что, например, мы имеем PSPACE = NPSPACE .

Предположим, что C — это класс сложности задач принятия решений , разрешимых в логарифмическом пространстве с вероятностными машинами Тьюринга , которые никогда не принимают неправильно, но которым разрешено отклонять неправильно менее чем в 1/3 случаев; это называется односторонней ошибкой . Константа 1/3 произвольна; подойдет любое x с 0 ≤ x < 1/2.

Оказывается, что C = NL . Обратите внимание, что C , в отличие от своего детерминированного аналога L , не ограничен полиномиальным временем, поскольку, хотя он имеет полиномиальное число конфигураций, он может использовать случайность, чтобы избежать бесконечного цикла. Если мы ограничим его полиномиальным временем, мы получим класс RL , который содержится в , но не известен или не считается равным NL .

Существует простой алгоритм, который устанавливает, что C = NL . Очевидно, что C содержится в NL , поскольку:

• Если строка отсутствует в языке, оба варианта отклоняются по всем путям вычислений.
• Если строка находится на языке, алгоритм NL принимает ее по крайней мере на одном пути вычислений, а алгоритм C принимает ее по крайней мере на двух третях своих путей вычислений.

Чтобы показать, что NL содержится в C , мы просто берем алгоритм NL и выбираем случайный путь вычислений длины n и выполняем его 2 ⁿ раз. Поскольку ни один путь вычислений не превышает длины n и поскольку всего существует 2 ⁿ путей вычислений, у нас есть хорошие шансы попасть в принимающий (ограниченный снизу константой).

Единственная проблема в том, что у нас нет места в логарифмическом пространстве для двоичного счетчика, который доходит до 2 ⁿ . Чтобы обойти это, мы заменяем его рандомизированным счетчиком, который просто подбрасывает n монет и останавливается и отклоняет, если все они приземляются орлом. Поскольку вероятность этого события составляет 2 ^{− n} , мы ожидаем , что в среднем он сделает 2 ⁿ шагов, прежде чем остановится. Ему нужно только хранить текущую сумму количества орлов в ряду, которые он видит, которую он может подсчитать в логарифмическом пространстве.

Из-за теоремы Иммермана–Селепчени , согласно которой NL замкнут относительно дополнений, односторонняя ошибка в этих вероятностных вычислениях может быть заменена нулевой ошибкой. То есть, эти проблемы могут быть решены вероятностными машинами Тьюринга, которые используют логарифмическое пространство и никогда не делают ошибок. Соответствующий класс сложности, который также требует от машины использования только полиномиального времени, называется ZPLP.

Таким образом, если рассматривать только пространство, то кажется, что рандомизация и недетерминизм одинаково сильны.

NL может быть эквивалентно охарактеризован сертификатами , аналогичными таким классам, как NP . Рассмотрим детерминированную машину Тьюринга с ограниченной логарифмической памятью, которая имеет дополнительную входную ленту только для чтения и однократного чтения. Язык находится в NL тогда и только тогда, когда такая машина Тьюринга принимает любое слово в языке для соответствующего выбора сертификата в своей дополнительной входной ленте и отклоняет любое слово, не принадлежащее языку, независимо от сертификата. ^[1]

Джем Сай и Абузер Якарыылмаз доказали, что детерминированная машина Тьюринга с логарифмическим пространством в приведенном выше утверждении может быть заменена вероятностной машиной Тьюринга с ограниченной ошибкой и постоянным пространством, которой разрешено использовать только постоянное число случайных битов. ^[2]

Существует простая логическая характеристика NL : он содержит именно те языки, которые можно выразить в логике первого порядка с добавленным оператором транзитивного замыкания .

Класс NL замкнут относительно операций дополнения, объединения и, следовательно, пересечения, конкатенации и звезды Клини .

• Зоопарк сложности : NL
• Пападимитриу, К. (1994). "Глава 16: Логарифмическое пространство". Computational Complexity . Addison-Wesley. ISBN 0-201-53082-1.
• Майкл Сипсер (27 июня 1997 г.). "Разделы 8.4–8.6: Классы L и NL, NL-полнота, NL равно coNL". Введение в теорию вычислений . PWS Publishing. стр. 294–302. ISBN 0-534-94728-X.
• Введение в теорию сложности: Лекция 7. Одед Голдрайх. Предложение 6.1. Наше C — это то, что Голдрайх называет badRSPACE(log n).