Логарифмический преобразователь пространства

В теории сложности вычислений преобразователь логарифмического пространства (LST) представляет собой тип машины Тьюринга, используемый для редукции логарифмического пространства .

Преобразователь логарифмического пространства имеет три ленты:${\displaystyle М}$

• Входная лента, доступная только для чтения .
• Рабочая лента для чтения/записи (ограниченная максимум символами).${\displaystyle O(\log n)}$
• Выходная лента , предназначенная только для записи и однократной записи .

${\displaystyle М}$будет разработан для вычисления функции, вычисляемой в логарифмическом пространстве (где — алфавит входной и выходной лент). Если выполняется с на входной ленте, то при остановке машины на выходной ленте останется.${\displaystyle f\colon \Сигма ^{\ast }\rightarrow \Сигма ^{\ast }}$${\displaystyle \Сигма}$${\displaystyle М}$${\displaystyle w}$${\displaystyle f(w)}$

Говорят, что язык сводится к языку с использованием логарифмического пространства , если существует вычислимая с использованием логарифмического пространства функция , которая преобразует входные данные из задачи во входные данные для задачи таким образом, что .${\displaystyle A\subseteq \Sigma ^{\ast }}$${\displaystyle B\subseteq \Sigma ^{\ast }}$ ${\displaystyle f}$${\displaystyle А}$${\displaystyle Б}$${\displaystyle w\in A\тогда и только тогда f(w)\in B}$

Это кажется довольно запутанной идеей, но у нее есть два полезных свойства, которые желательны для сокращения:

1. Свойство транзитивности сохраняется. (A сводится к B, а B сводится к C, влечет за собой A сводится к C).
2. Если A сводится к B, а B содержится в L , то мы знаем, что A содержится в L.

Транзитивность сохраняется, поскольку возможно подать выходную ленту одного редуктора (A→B) на другой (B→C). На первый взгляд, это кажется неправильным, поскольку редуктор A→C должен сохранить выходную ленту из редуктора A→B на рабочей ленте, чтобы подать ее в редуктор B→C, но это не так. Каждый раз, когда редуктору B→C требуется доступ к своей входной ленте, редуктор A→C может повторно запустить редуктор A→B, и поэтому выход редуктора A→B никогда не нужно сохранять полностью сразу.

• Шепетовски, Анджей (1994), Машины Тьюринга с сублогарифмическим пространством , Springer Press , ISBN  3-540-58355-6 . Получено 03.12.2008.
• Сипсер, Майкл (2012), Введение в теорию вычислений , Cengage Learning , ISBN 978-0-619-21764-8 .