Вычислимая функция в лог-пространстве

В теории сложности вычислений вычислимая функция в лог-пространстве — это функция $f\colon \Sigma ^{\ast }\rightarrow \Sigma ^{\ast }$ для этого требуется только $O(\log n)$ память , подлежащая вычислению (это ограничение не распространяется на размер вывода). Вычисления обычно выполняются с помощью преобразователя логарифмического пространства .

Сокращение пространства журнала

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

Примеры функций, вычислимых в лог-пространстве

• Функция преобразования задачи недетерминированной машины Тьюринга , которая решает язык A в лог-пространстве, в ST-связность .

Ссылки

• Сипсер, Майкл (2006), Введение в теорию вычислений , Cengage Learning , ISBN   978-0-619-21764-8 .