Л (сложность)
В сложности вычислений теории L (также известный как LSPACE или DLOGSPACE ) — это класс сложности , содержащий проблемы решения , которые могут быть решены детерминированной машиной Тьюринга с использованием логарифмического объема записываемого пространства памяти . [1] [2] Формально машина Тьюринга имеет две ленты, одна из которых кодирует ввод и доступна только для чтения. [3] тогда как другая лента имеет логарифмический размер, но ее можно читать так же, как и записывать. Логарифмического пространства достаточно для хранения постоянного количества указателей на вход. [1] и логарифмическое число логических флагов, и многие базовые алгоритмы пространства журналов используют память таким образом.
Полные задачи и логическая характеристика
[ редактировать ]Любая нетривиальная задача в L является полной при сокращении лог-пространства , [4] -полноты требуются более слабые редукции поэтому для выявления значимых понятий L , наиболее распространенными из которых являются первого порядка редукции .
Результат Омера Рейнгольда 2004 года показывает, что USTCON , проблема существования пути между двумя вершинами в данном неориентированном графе , находится в L , показывая, что L = SL , поскольку USTCON является SL -полным. [5]
Одним из следствий этого является простая логическая характеристика L : он содержит именно те языки, которые выражаются в логике первого порядка , с добавленным коммутативным транзитивным оператором замыкания (в терминах теории графов это превращает каждый компонент связности в клику ). Этот результат применим к языкам запросов к базам данных : сложность данных запроса определяется как сложность ответа на фиксированный запрос, учитывая размер данных в качестве входной переменной. Для этой меры запросы к реляционным базам данных с полной информацией (без понятия null ), как это выражается, например, в реляционной алгебре, в L. находятся
Связанные классы сложности
[ редактировать ]L является подклассом NL , который является классом языков, разрешимых в логарифмическом пространстве на недетерминированной машине Тьюринга . Проблема в NL может быть преобразована в проблему достижимости в ориентированном графе, представляющем состояния и переходы между состояниями недетерминированной машины, а граница логарифмического пространства подразумевает, что этот граф имеет полиномиальное число вершин и ребер, из чего следует, что NL содержится в классе сложности P задач, решаемых за детерминированное полиномиальное время. [6] Таким образом L ⊆ NL ⊆ P. , Включение L в P также можно доказать более непосредственно: решатель, использующий пространство O (log n ), не может использовать более 2 О ( войти ) = п О (1) время, потому что это общее количество возможных конфигураций.
L далее относится к классу NC следующим образом: Северная Каролина 1 ⊆ Л ⊆ НЛ ⊆ НК 2 . Другими словами, дан параллельный компьютер C с полиномиальным числом O ( n к ) процессоров для некоторой константы k , любая проблема, которая может быть решена на C за O (log n ) времени, находится за L , а любая проблема в L может быть решена за O (log 2 n время на C. )
Важные открытые проблемы включают в себя вопрос о том, L = P , [2] и является ли L = NL . [7] Неизвестно даже, является ли L = NP . [8]
Родственный класс функциональных задач — FL . FL часто используется для определения сокращения пространства журнала .
Дополнительные свойства
[ редактировать ]L сам по себе мал . , потому что он может имитировать запросы оракула в пространстве журнала (грубо говоря, «вызовы функций, которые используют пространство журнала») в пространстве журнала, повторно используя одно и то же пространство для каждого запроса
Другое использование
[ редактировать ]Основная идея пространства журнала заключается в том, что в пространстве журнала можно хранить число полиномиальной величины и использовать его для запоминания указателей на позицию ввода.
Таким образом, класс пространства журналов полезен для моделирования вычислений, когда входные данные слишком велики, чтобы поместиться в ОЗУ компьютера. Длинные последовательности ДНК и базы данных являются хорошими примерами проблем, когда только постоянная часть входных данных будет находиться в оперативной памяти в данный момент и где у нас есть указатели для вычисления следующей части входных данных для проверки, таким образом, используя только логарифмическую память.
См. также
[ редактировать ]- L/poly , неоднородный вариант L, который отражает сложность программ ветвления полиномиального размера.
Примечания
[ редактировать ]- ^ Перейти обратно: а б Сипсер (1997) , с. 295, Определение 8.12.
- ^ Перейти обратно: а б Гари и Джонсон (1979) , с. 177
- ^ На входной ленте для чтения/записи линейный объем памяти может быть получен путем упаковки символов (как в доказательстве теоремы о линейном ускорении ), что позволяет обойти ограничение пространства журнала.
- ^ См. Гари и Джонсон (1979) , с. 179, Теорема 7.13 (п. 2).
- ^ Рейнгольд, Омер (2005). Ненаправленная ST-связность в пространстве журналов . STOC'05: Материалы 37-го ежегодного симпозиума ACM по теории вычислений . АКМ, Нью-Йорк. стр. 376–385. дои : 10.1145/1060590.1060647 . МР 2181639 . ЕССС ТР04-094 .
- ^ Сипсер (1997) , Следствие 8.21, с. 299.
- ^ Сипсер (1997) , с. 297; Гари и Джонсон (1979) , с. 180
- ^ «Теория сложности — возможно ли, что L = NP» .
Ссылки
[ редактировать ]- Арора, Санджив; Барак, Вооз (2009). Вычислительная сложность. Современный подход . Издательство Кембриджского университета . ISBN 978-0-521-42426-4 . Збл 1193.68112 .
- Пападимитриу, Христос (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. Глава 16: Логарифмическое пространство, стр. 395–408. ISBN 0-201-53082-1 .
- Сипсер, Майкл (1997). Введение в теорию вычислений . Издательство ПВС. Раздел 8.4: Классы L и NL, стр. 294–296. ISBN 0-534-94728-Х .
- Гэри, MR ; Джонсон, DS (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. Раздел 7.5: Логарифмическое пространство, стр. 177–181 . ISBN 0-7167-1045-5 . МР 0519066 . OCLC 247570676 .
- Кук, Стивен А .; Маккензи, Пьер (1987). «Выполненные задачи для детерминированного логарифмического пространства» (PDF) . Журнал алгоритмов . 8 (3): 385–394. дои : 10.1016/0196-6774(87)90018-6 . ISSN 0196-6774 .