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

А вычислимая функция в лог-пространстве это функция это требует только память для вычисления (это ограничение не распространяется на размер вывода). Вычисления обычно выполняются с помощью преобразователь лог-пространства.

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

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

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

Примечания

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

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

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