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

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

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

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

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