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

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

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

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

В теории сложности вычислений , Н.Л. ( N ondeterministic л ogarithmic-пространство) является класс сложности , содержащие проблемы решения , которые могут быть решены с помощью недетерминированной машины Тьюринга , используя логарифмическую величину пространства памяти .

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

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

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

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

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

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

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

{\ Displaystyle {\ mathsf {NC_ {1} \ substeq L \ substeq NL \ substeq NC_ {2}}}}

.

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

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

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

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

Альтернативные определения

Вероятностное определение

Предположим , что C является класс сложности из задач решения разрешима в пространстве logarithmithic с вероятностными машинами Тьюринга , которые никогда не принимают неправильно , но разрешено отклонять неправильно менее чем 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 тогда и только тогда, когда такая машина Тьюринга принимает любое слово на языке для соответствующего выбора сертификата на своей дополнительной входной ленте и отклоняет любое слово не на этом языке, независимо от сертификата.

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

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

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

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

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

Languages

In other projects