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

Нерешенная проблема в информатике: ${\displaystyle {\mathsf {L{\overset {?}{=}}NL}}}$ (больше нерешенных проблем в информатике)

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

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

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

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

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

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

Известно несколько проблем. NL-полный под сокращение пространства журнала, включая ST-подключение и 2-выполнимость. ST-подключение запрашивает узлы 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 содержится в п, так как есть полиномиальный алгоритм за 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{equivalently, }}{\mathsf {NL\subseteq L}}^{2}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Арора, Санджив; Варак, Вооз (2009). «Определение 4.19». Теория сложности: современный подход. Издательство Кембриджского университета. ISBN  978-0-521-42426-4.

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

• Зоопарк сложности: NL
• Пападимитриу, К. (1994). «Глава 16: Логарифмическое пространство». Вычислительная сложность. Эддисон-Уэсли. 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).