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

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

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

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

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

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

Примечания

1. Сипсер (2006) Международное второе издание, стр. 328.

Рекомендации

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