В теории сложности вычислений , L (также известный как LSPACE или DLOGSPACE ) является класс сложности , содержащие проблемы решения , которые могут быть решены с помощью детерминированной машины Тьюринга , используя логарифмическое количество записываемой области памяти . [1] [2] Формально машина Тьюринга имеет две ленты, одна из которых кодирует ввод и может быть только прочитана, тогда как другая лента имеет логарифмический размер, но может быть прочитана так же, как и записана. Логарифмического пространства достаточно для хранения постоянного числа указателей на входе [1] и логарифмическое количество логических флагов, и многие базовые алгоритмы пространства журнала используют память таким образом.
Полные задачи и логическая характеристика
Каждая нетривиальная задача в L является полной при сокращении логарифмического пространства , [3] , так слабее сокращения необходимы для выявления значимых понятий L -полноты, наиболее распространенных являются первые порядка сокращения .
Результат Омера Рейнгольда 2004 года показывает, что USTCON , проблема существования пути между двумя вершинами в данном неориентированном графе , находится в L , показывая, что L = SL , поскольку USTCON является SL -полным. [4]
Одним из следствий этого является простая логическая характеристика L : он содержит именно те языки, которые можно выразить в логике первого порядка с добавленным коммутативным транзитивным оператором замыкания (в терминах теории графов , это превращает каждый компонент связности в клику ). Этот результат применим к языкам запросов к базам данных : сложность данных запроса определяется как сложность ответа на фиксированный запрос с учетом размера данных как входной переменной. Для этой меры, запросы к реляционным базам данных с полной информацией (не имеющей никакого понятия нулям ) , что выражается, например , в реляционной алгебре в L .
Связанные классы сложности
L является подклассом NL , который является классом языков, разрешимых в логарифмическом пространстве на недетерминированной машине Тьюринга . Проблема в NL может быть преобразована в проблему достижимости в ориентированном графе, представляющем состояния и переходы состояний недетерминированной машины, а логарифмическая граница пространства подразумевает, что этот граф имеет полиномиальное количество вершин и ребер, из чего следует, что NL содержится в классе сложности P задач, разрешимых за детерминированное полиномиальное время. [5] Таким образом , 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 , [2] и является ли L = NL . [6] Неизвестно даже, было ли L = NP . [7]
Родственный класс функциональных проблем - FL . FL часто используется для определения сокращения пространства журнала .
Дополнительные свойства
L является низким для себя, потому что он может имитировать лог-пространства оракула запросов (грубо говоря, «вызовы функций, использование которых пространство журнала») в пространство журнала, повторное использование и то же пространство для каждого запроса.
Другое использование
Основная идея logspace состоит в том, что можно хранить число полиномиальной величины в logspace и использовать его для запоминания указателей на позицию ввода.
Поэтому класс logspace полезен для моделирования вычислений, когда входные данные слишком велики, чтобы поместиться в ОЗУ компьютера. Длинные последовательности ДНК и базы данных являются хорошими примерами проблем, когда только постоянная часть ввода будет в ОЗУ в данный момент времени и где у нас есть указатели для вычисления следующей части ввода для проверки, таким образом, используя только логарифмическую память.
Смотрите также
- L / poly , неоднородный вариант L, который отражает сложность программ ветвления полиномиального размера
Заметки
- ^ a b Sipser (1997) , определение 8.12, стр. 295.
- ^ a b Garey & Johnson (1979) , стр. 177.
- ^ См. Garey & Johnson (1979) , теорема 7.13 (утверждение 2), стр. 179.
- Перейти ↑ Reingold, Omer (2005). Ненаправленное ST-соединение в лог-пространстве . STOC'05: Материалы 37-го ежегодного симпозиума ACM по теории вычислений . ACM, Нью-Йорк. С. 376–385. DOI : 10.1145 / 1060590.1060647 . Руководство по ремонту 2181639 . ECCC TR04-094 .
- ^ Sipser (1997) , следствие 8.21, стр. 299.
- ^ Sipser (1997) , стр. 297; Garey & Johnson (1979) , стр. 180.
- ^ https://cs.stackexchange.com/questions/103073/is-it-possible-that-l-np
Рекомендации
- Арора, Санджив ; Варак, Вооз (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 .