Введение
Класс сложности (логарифмическое пространство)
В теории вычислительной сложности L (также известный как LSPACE или DLOGSPACE) — это класс сложности, содержащий задачи принятия решений, которые могут быть решены детерминированной машиной Тьюринга, используя логарифмический объем записываемой памяти. Формально, машина Тьюринга имеет две ленты, одна из которых кодирует входные данные и может только читаться, в то время как другая лента имеет логарифмический размер, но может как читаться, так и записываться. Логарифмического пространства достаточно для хранения постоянного числа указателей на входные данные, поэтому для определения значимых понятий L-полноты требуются более слабые приведения, наиболее распространенными из которых являются приведения первого порядка. Результат 2004 года Омера Рейнгольда показывает, что задача USTCON (определение наличия пути между двумя вершинами в заданном неориентированном графе) принадлежит классу L, что доказывает равенство L = SL, поскольку USTCON является SL-полной задачей. Одним из следствий этого является простая логическая характеристика L: она содержит ровно те языки, которые могут быть выражены в логике первого порядка с добавлением коммутативного транзитивного оператора замыкания (в терминах теории графов это превращает каждую связную компоненту в клику). Этот результат применим к языкам запросов баз данных: сложность данных для запроса определяется как сложность ответа на фиксированный запрос при рассмотрении размера данных в качестве переменной входной информации. Для этой меры запросы к реляционным базам данных с полной информацией (не содержащим понятия null-значений), выраженные, например, на реляционной алгебре, принадлежат классу L.
Дополнительные свойства
L является низким для себя, поскольку он может имитировать запросы к оракулу в логарифмическом пространстве (грубо говоря, "вызовы функций, использующих логарифмическое пространство") в логарифмическом пространстве, повторно используя одно и то же пространство для каждого запроса.
Другие применения
Основная идея логпространства заключается в том, что можно хранить число, величина которого растёт полиномиально, в логпространстве и использовать его для запоминания указателей на позицию входных данных. Таким образом, класс логпространства полезен для моделирования вычислений, когда входные данные слишком велики, чтобы поместиться в оперативную память компьютера. Длинные последовательности ДНК и базы данных — хорошие примеры задач, в которых в любой момент времени в оперативной памяти находится лишь небольшая часть входных данных, и у нас есть указатели для вычисления следующей части входных данных для анализа, что позволяет использовать лишь логарифмический объём памяти.