Введение
В теории вычислительной сложности, NL (Nondeterministic Logarithmic space) – это класс сложности, содержащий задачи принятия решений, которые могут быть решены недетерминированной машиной Тьюринга, используя логарифмический объём памяти. NL является обобщением класса L, предназначенного для задач, решаемых в логарифмическом пространстве на детерминированной машине Тьюринга. Поскольку любая детерминированная машина Тьюринга также является недетерминированной, L содержится в NL. NL может быть формально определен с точки зрения вычислительного ресурса – недетерминированного пространства (или NSPACE) – как NL = NSPACE(log n). Важные результаты в теории сложности позволяют соотносить этот класс сложности с другими, давая представление об относительной мощности соответствующих ресурсов. Результаты в области алгоритмов, в свою очередь, показывают, какие задачи можно решить, используя этот ресурс. Как и в большей части теории сложности, многие важные вопросы, касающиеся NL, остаются открытыми (см. Нерешенные проблемы в информатике). Иногда NL называют RL из-за его вероятностного определения, представленного ниже; однако это название чаще используется для обозначения рандомизированного логарифмического пространства, равенство которого с NL пока не доказано.
NL-полные проблемы
Известно несколько задач, являющихся NP-полными при логарифмических сведении, включая ST-связность и 2-удовлетворимость. ST-связность спрашивает, достижим ли узел T из узла S в ориентированном графе. 2-удовлетворимость спрашивает, существует ли такая подстановка значений переменным в пропозициональной формуле, где каждый дизъюнкт состоит из двух литералов, при которой формула становится истинной. Например, формула с отрицанием (обозначаемым ¬) может выглядеть так:
Контейнеры
Известно, что содержится в , поскольку существует алгоритм полиномиального времени для 2-удовлетворимости, но неизвестно, содержится ли в или нет. Известно, что , где – класс языков, комплементы которых находятся в . Этот результат (теорема Иммермана — Сзелепчени) был независимо открыт Нилом Иммерманом и Робертом Сзелепчени в 1987 году; они получили премию Гёделя за эту работу в 1995 году. В сложности схем, можно поместить в иерархию . В Papadimitriou 1994, Теорема 16.1, мы имеем:
More precisely, is contained in It is known that is equal to , the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to or , the polynomial time restrictions of and , which some authors refer to as and
We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:
This was the strongest deterministic space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have .
Более точно, содержится в . Известно, что равен , классу задач, разрешимых рандомизированными алгоритмами в логарифмическом пространстве и неограниченном времени без ошибок. Однако не известно и не предполагается, что он равен или , полиномиальным ограничениям по времени для и , которые некоторые авторы называют и .
More precisely, is contained in It is known that is equal to , the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to or , the polynomial time restrictions of and , which some authors refer to as and
We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:
This was the strongest deterministic space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have .
Мы можем связать с детерминированным пространством, используя теорему Савича, которая утверждает, что любой недетерминированный алгоритм может быть смоделирован детерминированной машиной, используя не более чем квадратично больше пространства. Непосредственно из теоремы Савича следует:
More precisely, is contained in It is known that is equal to , the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to or , the polynomial time restrictions of and , which some authors refer to as and
We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:
This was the strongest deterministic space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have .
Это было сильнейшее известное в 1994 году включение детерминированного пространства (Papadimitriou 1994, Проблема 16.4.10, "Симметричное пространство"). Поскольку квадратичные увеличения не влияют на большие классы пространства, недетерминированные и детерминированные классы известны как равные, так что, например, у нас есть .
More precisely, is contained in It is known that is equal to , the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to or , the polynomial time restrictions of and , which some authors refer to as and
We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:
This was the strongest deterministic space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have .
Вероятностное определение
Предположим, C — это класс сложности задач принятия решений, разрешимых в логарифмическом пространстве с помощью вероятностных машин Тьюринга, которые никогда не принимают неверно, но могут отклонять неверно менее чем в 1/3 случаев; это называется ошибкой с одной стороны. Константа 1/3 произвольна; любое x, удовлетворяющее условию 0 ≤ x < 1/2, будет достаточно. Оказывается, что C = NL. Обратите внимание, что C, в отличие от своего детерминированного аналога L, не ограничивается полиномиальным временем, поскольку, хотя у него полиномиальное количество конфигураций, он может использовать случайность, чтобы избежать бесконечного цикла. Если мы ограничим его полиномиальным временем, мы получим класс RL, который содержится в NL, но не известно и не предполагается, что он равен NL. Существует простой алгоритм, который устанавливает, что C = NL. Очевидно, что C содержится в NL, поскольку: если строка не принадлежит языку, она отклоняется по всем путям вычислений. Если строка принадлежит языку, то NL-алгоритм принимает по крайней мере на одном пути вычисления, а C-алгоритм принимает по крайней мере на двух третях своих путей вычисления. Чтобы показать, что NL содержится в C, мы просто берем NL-алгоритм и выбираем случайный путь вычисления длиной n, и выполняем это 2n раз. Поскольку ни один путь вычисления не превышает длины n, и поскольку существует 2n путей вычисления, у нас есть хороший шанс попасть в принимающий путь (ограниченный снизу константой). Единственная проблема в том, что у нас нет места в логарифмическом пространстве для двоичного счетчика, который достигает значения 2n. Чтобы обойти это, мы заменяем его рандомизированным счетчиком, который просто подбрасывает n монет и останавливается и отклоняет, если все они выпадают орлом. Поскольку вероятность этого события равна 2−n, мы ожидаем сделать в среднем 2n шагов перед остановкой. Ему нужно только хранить текущее количество выпавших подряд орлов, которое он может подсчитать в логарифмическом пространстве. Благодаря теореме Иммермана — Сзелепчени, согласно которой NL замкнута относительно дополнений, ошибку с одной стороны в этих вероятностных вычислениях можно заменить на ошибку с нулем сторон. То есть эти задачи могут быть решены вероятностными машинами Тьюринга, которые используют логарифмическое пространство и никогда не совершают ошибок. Соответствующий класс сложности, который также требует, чтобы машина использовала только полиномиальное время, называется ZPLP. Таким образом, если мы рассматриваем только пространство, то кажется, что рандомизация и недетерминизм одинаково мощны.
If the string is not in the language, both reject along all computation paths. If the string is in the language, an NL algorithm accepts along at least one computation path and a C algorithm accepts along at least two thirds of its computation paths. To show that NL is contained in C, we simply take an NL algorithm and choose a random computation path of length n, and execute this 2n times. Because no computation path exceeds length n, and because there are 2n computation paths in all, we have a good chance of hitting the accepting one (bounded below by a constant). The only problem is that we don't have room in log space for a binary counter that goes up to 2n. To get around this we replace it with a randomized counter, which simply flips n coins and stops and rejects if they all land on heads. Since this event has probability 2−n, we expect to take 2n steps on average before stopping. It only needs to keep a running total of the number of heads in a row it sees, which it can count in log space. Because of the Immerman–Szelepcsényi theorem, according to which NL is closed under complements, the one sided error in these probabilistic computations can be replaced by zero sided error. That is, these problems can be solved by probabilistic Turing machines that use logarithmic space and never make errors. The corresponding complexity class that also requires the machine to use only polynomial time is called ZPLP. Thus, when we only look at space, it seems that randomization and nondeterminism are equally powerful.
Определение сертификата
NL может быть эквивалентно характеризована сертификатами, аналогично классам, таким как NP. Рассмотрим детерминированную машину Тьюринга с логарифмическим ограничением по памяти, имеющую дополнительную ленту, предназначенную только для однократного чтения входных данных. Язык принадлежит классу NL тогда и только тогда, когда такая машина Тьюринга принимает любое слово, принадлежащее языку, при соответствующем выборе сертификата на дополнительной входной ленте, и отклоняет любое слово, не принадлежащее языку, независимо от выбранного сертификата. Джем Сай и Абузер Якарылмаз доказали, что детерминированную машину Тьюринга с логарифмическим ограничением по памяти, описанную выше, можно заменить вероятностной машиной Тьюринга с ограниченной ошибкой и постоянным объемом памяти, которой разрешено использовать только постоянное количество случайных битов.
Описательная сложность
Существует простое логическое описание NL: она включает в себя ровно те языки, которые можно выразить в логике первого порядка с добавленным оператором транзитивного замыкания.
Свойства закрытия
Класс NL замкнут относительно операций дополнения, объединения и, следовательно, пересечения, конкатенации и звезды Клине.