L (сложность)
-
Определение и характеристики класса L
- L — класс задач, решаемых детерминированной машиной Тьюринга с логарифмической памятью.
- Машина Тьюринга имеет две ленты: для ввода и логарифмического размера, обе могут быть считаны и записаны.
- Логарифмическое пространство достаточно для хранения указателей на данные и логических флагов.
-
Полнота и логическая характеристика L
- Каждая нетривиальная задача в L является полной при логарифмическом сокращении пространства.
- L содержит языки, которые можно выразить в логике первого порядка с коммутативным оператором транзитивного замыкания.
- Запросы к базам данных с полной информацией выполняются на языке L.
-
Связь с другими классами сложности
- L является подклассом NL, который относится к классу P разрешимых задач в детерминированное полиномиальное время.
- L также относится к классу NC, что означает, что задачи, решаемые за O(log n) времени на параллельном компьютере с полиномиальным числом процессоров, находятся в L.
-
Открытые проблемы и приложения
- Неизвестны точные границы между L и P, L и NL, а также L и NP.
- L используется для моделирования вычислений с большими входными данными, которые не помещаются в оперативную память.
- Длинные последовательности ДНК и базы данных являются примерами проблем, где используется логарифмическая память.
-
Дополнительные свойства и приложения
- L может имитировать запросы oracle в логарифмическом пространстве.
- L/ poly — неоднородный вариант L, отражающий сложность программ ветвления полиномиального размера.
Полный текст статьи: