NL (сложность)
-
Определение и свойства NL
- NL — класс задач решения, решаемых недетерминированной машиной Тьюринга с логарифмическим объемом памяти.
- NL обобщает L, класс задач с логарифмическим пространством на детерминированных машинах Тьюринга.
- NL может быть формально определен как NSPACE(log n).
-
Связь с другими классами сложности
- NL связан с другими классами сложности, указывая на относительную мощность ресурсов.
- Алгоритмы позволяют определить, какие проблемы могут быть решены с использованием NL.
-
Нерешенные проблемы в теории сложности
- Многие важные вопросы о NL остаются открытыми.
-
Примеры NL-полных задач
- Некоторые задачи, связанные с ST-связностью и 2-удовлетворяемостью, являются NL-полными.
-
Сдерживающие факторы и теоремы
- NL содержится в P, но неизвестно, равно ли оно P или L.
- NL = co-NL, что было доказано Иммерманом и Шелепчени в 1987 году.
- NL может быть отнесено к иерархии ЧПУ.
-
Альтернативные определения и свойства
- Вероятностное определение NL включает задачи, решаемые с помощью вероятностных машин Тьюринга с ограниченной ошибкой.
- NL может быть охарактеризован сертификатами, аналогичными классам NP.
- NL закрыт относительно операций дополнения, объединения и пересечения.
-
Описательная сложность и свойства закрытия
- NL содержит языки, которые могут быть выражены в логике первого порядка с добавлением оператора транзитивного замыкания.
-
Рекомендации
- Ссылки на дополнительные материалы по теории сложности и NL.
Полный текст статьи: