Л (сложность)

«Пространство журналов» перенаправляется сюда. Не путать с Logscale .

В сложности вычислений теории L (также известный как LSPACE или DLOGSPACE ) — это класс сложности , содержащий проблемы решения , которые могут быть решены детерминированной машиной Тьюринга с использованием логарифмического объема записываемого пространства памяти . Формально машина Тьюринга имеет две ленты, одна из которых кодирует ввод и доступна только для чтения. тогда как другая лента имеет логарифмический размер, но ее можно читать так же, как и записывать. Логарифмического пространства достаточно для хранения постоянного количества указателей на вход. и логарифмическое число логических флагов, и многие базовые алгоритмы пространства журналов используют память таким образом.

и

Любая нетривиальная задача в L является полной при сокращении лог-пространства , -полноты требуются более слабые редукции поэтому для выявления значимых понятий L , наиболее распространенными из которых являются первого порядка редукции .

Результат Омера Рейнгольда, полученный в 2004 году, показывает, что USTCON , проблема существования пути между двумя вершинами в данном неориентированном графе , находится в L , показывая, что L = SL , поскольку USTCON является SL -полным.

Одним из следствий этого является простая логическая характеристика L : он содержит именно те языки, которые выражаются в логике первого порядка , с добавленным коммутативным транзитивным оператором замыкания (в терминах теории графов это превращает каждый компонент связности в клику ). Этот результат применим к языкам запросов к базам данных : сложность данных запроса определяется как сложность ответа на фиксированный запрос, учитывая размер данных в качестве входной переменной. Для этой меры запросы к реляционным базам данных с полной информацией (без понятия null ), как это выражается, например, в реляционной алгебре, в L. находятся

Связанные классы сложности

L является подклассом NL , который является классом языков, разрешимых в логарифмическом пространстве на недетерминированной машине Тьюринга . Задача в NL может быть преобразована в проблему достижимости в ориентированном графе, представляющем состояния и переходы между состояниями недетерминированной машины, а из логарифмической границы пространства следует, что этот граф имеет полиномиальное число вершин и ребер, из чего следует, что NL содержится в классе сложности P задач, решаемых за детерминированное полиномиальное время. Таким образом L ⊆ NL ⊆ P. , Включение L в P также можно доказать более непосредственно: решатель, использующий пространство O (log n ), не может использовать более 2 ^{О (логарифм n )} = п ^{О (1)} время, потому что это общее количество возможных конфигураций.

L далее относится к классу NC следующим образом: Северная Каролина ¹ ⊆ Л ⊆ НЛ ⊆ НК ² .Другими словами, дан параллельный компьютер C с полиномиальным числом O ( n ^к ) процессоров для некоторой константы k , любая проблема, которую можно решить на C за O (log n ) времени, находится за L , а любая проблема в L может быть решена за O (log ²  n время на C. )

Нерешенная задача в информатике :

${\mathsf {L}}{\overset {?}{=}}{\mathsf {P}}$

(еще нерешенные проблемы по информатике)

Важные открытые проблемы включают в себя вопрос о том, L = P , и является ли L = NL . Неизвестно даже, является ли L = NP .

Родственный класс функциональных задач — FL . FL часто используется для определения сокращения пространства журнала .

Дополнительные свойства

L сам по себе мал . , потому что он может имитировать запросы оракула в пространстве журнала (грубо говоря, «вызовы функций, которые используют пространство журнала») в пространстве журнала, повторно используя одно и то же пространство для каждого запроса

Другое использование

Основная идея пространства журнала заключается в том, что в пространстве журнала можно хранить число полиномиальной величины и использовать его для запоминания указателей на позицию ввода.

Таким образом, класс пространства журналов полезен для моделирования вычислений, когда входные данные слишком велики, чтобы поместиться в ОЗУ компьютера. Длинные последовательности ДНК и базы данных являются хорошими примерами проблем, когда только постоянная часть входных данных будет находиться в оперативной памяти в определенный момент времени и где у нас есть указатели для вычисления следующей части входных данных для проверки, таким образом, используя только логарифмическую память.

См. также

• L/poly , неоднородный вариант L, который отражает сложность программ ветвления полиномиального размера.

Ссылки

• Арора, Санджив; Барак, Вооз (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 .