Оглавление
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.
Полный текст статьи: