NL-полный
-
Определение и свойства NL-complete
- NL-complete — класс сложности, включающий задачи, решаемые недетерминированной машиной Тьюринга с логарифмической памятью.
- Задачи в NL-complete являются самыми «сложными» или «выразительными» в NL.
- Если существует детерминированный алгоритм для решения NL-полной задачи в логарифмическом пространстве, то NL = L.
-
Определение NL и L
- NL включает задачи, решаемые недетерминированными машинами с ограниченной памятью, пропорциональной логарифму длины ввода.
- L состоит из языков, решаемых детерминированными машинами Тьюринга с теми же ограничениями на память.
- Оба класса являются подмножествами P, класса детерминированных задач с полиномиальным временем решения.
-
Теорема Иммермана-Шелепчени
- Если язык является ко-NL-полным, то он сам является NL-полным.
-
Примеры NL-полных задач
- ST-связность — задача определения существования пути между двумя узлами в графе.
- 2-удовлетворяемость — задача определения выполнимости булевой формулы с двумя переменными.
- Риттер показал, что однозначная расшифровка кода переменной длины является ко-NL-полной.
-
Дополнительные NL-полные задачи
- В книге Джонса (1976) перечислены другие задачи из логики высказываний, алгебры, линейных систем, графов, конечных автоматов и контекстно-свободных грамматик.
-
Рекомендации по форматированию
- Статья содержит инструкции по форматированию библиографических описаний и других элементов в HTML.
Полный текст статьи: