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

Нерешенная задача в информатике :

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

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

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

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

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

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

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

NL-полные задачи

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

$(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 . В теореме 16.1 Пападимитриу 1994 мы имеем:

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

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

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

${\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{equivalently, }}{\mathsf {NL\subseteq L}}^{2}.$

Это было самое сильное включение в детерминированное пространство, известное в 1994 году (Пападимитриу, 1994, проблема 16.4.10, «Симметричное пространство»). Поскольку на более крупные пространственные классы квадратичные увеличения не влияют, известно, что недетерминированные и детерминированные классы равны, так что, например, мы имеем 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 ^{− п} , мы рассчитываем взять 2 ^н в среднем шагов до остановки. Ему нужно только хранить общее количество головок подряд, которые он видит, и которые он может подсчитать в пространстве журнала.

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

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

Определение сертификата

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

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

Описательная сложность

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

Свойства замыкания

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

Ссылки

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