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

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

Преобразователь пространства журнала, $M$ , имеет три ленты:

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

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

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

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

Свойство транзитивности имеет место. (А сводится к Б, а Б сводится к С, подразумевает, что А сводится к С).
Если 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 . Проверено 3 декабря 2008 г.
Сипсер, Майкл (2012), Введение в теорию вычислений , Cengage Learning , ISBN 978-0-619-21764-8 .

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .