L (сложность) - L (complexity)
В теории сложности вычислений , L (также известный как LSPACE или DLOGSPACE ) является класс сложности , содержащие проблемы решения , которые могут быть решены с помощью детерминированной машины Тьюринга , используя логарифмическое количество записываемой области памяти . Формально машина Тьюринга имеет две ленты, одна из которых кодирует ввод и может быть только прочитана, тогда как другая лента имеет логарифмический размер, но может быть прочитана так же, как и записана. Логарифмического пространства достаточно для хранения постоянного числа указателей на входе и логарифмического числа логических флагов, и многие базовые алгоритмы логарифмического пространства используют память таким образом.
Полные задачи и логическая характеристика
Каждая нетривиальная проблема в L является полной относительно сокращений в лог-пространстве , поэтому для выявления значимых понятий L -полноты требуются более слабые редукции , наиболее распространенными из которых являются редукции первого порядка .
Результат Омера Рейнгольда 2004 года показывает, что USTCON , проблема существования пути между двумя вершинами в данном неориентированном графе , находится в L , показывая, что L = SL , поскольку USTCON является SL- завершенным.
Одним из следствий этого является простая логическая характеристика L : он содержит именно те языки, которые можно выразить в логике первого порядка с добавленным коммутативным транзитивным оператором замыкания (в терминах теории графов , это превращает каждый компонент связности в клику ). Этот результат применим к языкам запросов к базам данных : сложность данных запроса определяется как сложность ответа на фиксированный запрос с учетом размера данных как входной переменной. Для этой меры, запросы к реляционным базам данных с полной информацией (не имеющей никакого понятия нулям ) , что выражается, например , в реляционной алгебре в L .
Связанные классы сложности
L является подклассом NL , который является классом языков, разрешимых в логарифмическом пространстве на недетерминированной машине Тьюринга . Проблема в NL может быть преобразована в проблему достижимости в ориентированном графе, представляющем состояния и переходы состояний недетерминированной машины, а логарифмическая граница пространства подразумевает, что этот граф имеет полиномиальное количество вершин и ребер, из чего следует, что NL содержится в классе сложности P задач, разрешимых за детерминированное полиномиальное время. Таким образом , L ⊆ NL ⊆ P . Включение L в P также можно доказать более прямо: принимающее решение, использующее пространство O (log n ), не может использовать более 2 O (log n ) = n O (1) раз, потому что это общее количество возможных конфигураций.
L далее относится к классу NC следующим образом: NC 1 ⊆ L ⊆ NL ⊆ NC 2 . Другими словами, учитывая параллельный компьютер C с полиномиальным числом процессоров O ( n k ) для некоторой константы k , любая проблема, которая может быть решена на C за время O (log n ), находится в L , и любая проблема в L может быть решена. решена в O (вход 2 н ) время на C .
Важные открытые проблемы включают в себя: L = P и L = NL . Неизвестно даже, было ли L = NP .
Связанный класс функциональных проблем - FL . FL часто используется для определения сокращения пространства журнала .
Дополнительные свойства
L является низким для себя, потому что он может имитировать лог-пространства оракула запросов (грубо говоря, «вызовы функций, использование которых пространство журнала») в пространство журнала, повторное использование и то же пространство для каждого запроса.
Другое использование
Основная идея logspace состоит в том, что в logspace можно сохранить число полиномиальной величины и использовать его для запоминания указателей на позицию ввода.
Поэтому класс logspace полезен для моделирования вычислений, когда входные данные слишком велики, чтобы поместиться в ОЗУ компьютера. Длинные последовательности ДНК и базы данных являются хорошими примерами проблем, когда только постоянная часть ввода будет в ОЗУ в данный момент времени и где у нас есть указатели для вычисления следующей части ввода для проверки, таким образом, используя только логарифмическую память.
Смотрите также
- L / poly , неоднородный вариант L, который отражает сложность программ ветвления полиномиального размера
Примечания
использованная литература
- Арора, Санджив ; Варак, Вооз (2009). Вычислительная сложность. Современный подход . Издательство Кембриджского университета . ISBN 978-0-521-42426-4. Zbl 1193.68112 .
- Пападимитриу, Христос (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. Глава 16. Логарифмическое пространство, стр. 395–408. ISBN 0-201-53082-1.
- Сипсер, Майкл (1997). Введение в теорию вычислений . PWS Publishing. Раздел 8.4: Классы L и NL, стр. 294–296. ISBN 0-534-94728-X.
- Garey, MR ; Джонсон, Д.С. (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . WH Freeman. Раздел 7.5: Логарифмическое пространство, стр. 177–181 . ISBN 0-7167-1045-5.
- Кук, Стивен А .; Маккензи, Пьер (1987). "Полные задачи для детерминированного логарифмического пространства" (PDF) . Журнал алгоритмов . 8 (3): 385–394. DOI : 10.1016 / 0196-6774 (87) 90018-6 . ISSN 0196-6774 .