Теорема о линейном ускорении

В теории сложности вычислений теорема линейного ускорения для машин Тьюринга гласит, что для любого реального c > 0 и любой k -ленточной машины Тьюринга, решающей задачу за время f ( n ), существует другая k -ленточная машина, которая решает ту же задачу за время f (n). время не более f ( n )/ c + 2 n + 3 , где k > 1. ^[1]^[2]Если исходная машина недетерминирована , то новая машина также недетерминирована.Константы 2 и 3 в 2 n + 3 можно уменьшить, например, до n + 2. ^[1]

Доказательство

Конструкция основана на упаковке нескольких ленточных символов исходной машины M в один ленточный символ новой N. машины Это имеет тот же эффект, что и использование более длинных слов и команд в процессорах: ускоряет вычисления, но увеличивает размер машины.Сколько старых символов упаковывается в новый, зависит от желаемого ускорения.

Предположим, новая машина упаковывает три старых символа в новый символ.Тогда алфавит новой машины будет $\Sigma \cup \Sigma ^{3}$ : состоит из исходных символов и упакованных символов.Новая машина имеет такое же количество k лент > 1.Состояние N состоит из следующих компонентов:

состояние М ;
для каждой ленты три упакованных символа, описывающих упакованный символ под заголовком, упакованный символ слева и упакованный символ справа; и
исходное положение головки внутри упакованного символа под заголовком N. для каждой ленты —

Новая машина N начинает с кодирования данных входных данных в новый алфавит (поэтому ее алфавит должен включать в себя $\Sigma$ ).Например, если вход на 2-ленту M находится слева, то после кодирования конфигурация ленты N находится справа:

[ #

_

а

б

а

б

а

_

...]

[ #

(_,_,_)

...]

[ #

_

...]

[ #

(_,а,б)

(б, а, б)

(б,а,_)

...]

Новая машина упаковывает три старых символа (например, пустой символ _ , символ a и символ b ) в новый символ (здесь (_, a , b )) и копирует его на вторую ленту, стирая при этом первую ленту. .По окончании инициализации новая машина направляет голову в начало.В целом это занимает 2n + 3 шага.

После инициализации состояние N равно $(q_{0};~~~?,(\_,\_,\_),?;~~~?,(\_,a,b),?;~~~[1,1])$ , где символ $?$ означает, что он будет заполнен машиной позже; символ $[1,1]$ означает, что голова исходной машины указывает на первые символы внутри $(\_,\_,\_)$ и $(\_,a,b)$ . Теперь машина начинает моделировать m = 3 перехода M, используя шесть своих собственных переходов (в данном конкретном случае ускорения не будет, но вообще m может быть намного больше шести).Пусть конфигурации M и N будут:

[ #

_

б

а

б

а

_

...]

[ #

(_,а,б)

(б, а, б)

( б ,_,_)

...]

[ #

_

а

б

а

б

_

...]

[ #

(_,_, б )

(б, а, б)

(б,а,_)

...]

где жирные символы указывают положение головы.Состояние N $(q;~~~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])$ .Теперь происходит следующее:

N движется вправо, влево, влево, вправо. После четырех ходов машина N имеет все свои возможности . $?$ заполняется, и его состояние становится $(q;~~~\#,(\_,\_,b),(b,a,b);~~~(b,a,b),(b,\_,\_),(\_,\_,\_);~~~[3,1])$
Теперь N обновляет свои символы и состояние в соответствии с m = 3 переходами исходной машины. Для этого может потребоваться два хода (обновить текущий символ и обновить один из соседних с ним символов). Предположим, что исходная машина движется следующим образом (с соответствующей конфигурацией N справа):

[ #

_

б

а

_

...]

[ #

(_,а,б)

( б ,_,_)

(_,_,_)

...]

[ #

_

а

б

_

...]

[ #

(_,_,_)

(_,_, б )

(б,а,_)

...]

Таким образом, состояние N становится $(q';~~~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])$ .

Сложность

Инициализация требует 2 n + 3 шагов. В симуляции 6 шагов N моделируют m шагов M . Выбор m > 6 c дает время работы, ограниченное $f(n)/c+2n+3.$

Машины с входной лентой только для чтения

Теорема, сформулированная выше, справедлива и дляМашины Тьюринга с односторонней входной лентой только для чтенияи $k\geq 1$ рабочие ленты. ^[3]

Одноленточные машины

Для одноленточных машин Тьюринга линейное ускорение сохраняется для машин со временем выполнения не менее $n^{2}$ . Это, очевидно, не справедливо для машин со временем. $t(n)\in \Omega (n\log n)\cap o(n^{2})$ . ^[3]

Зависимость от сжатия ленты

Доказательство теоремы об ускорении явно зависит от возможности сжатия памяти путем замены алфавита на более крупный.Гефферт ^[4] показал, что для недетерминированные одноленточные машины Тьюринга временной сложности $T(n)\geq n^{2}$ линейного ускорения можно добиться без увеличения алфавита.

Зависимость от формы хранения

Риган ^[5] считается свойством вычислительной модели, называемым информационной окрестностью. Это свойство связано со структурой памяти: машина Тьюринга имеет линейную окрестность, а машина Колмогорова-Успенского и другие указательные машины — экспоненциальную. Тезис Ригана заключается в том, что существование линейного ускорения связано с наличием полиномиальной информационной близости. Важным моментом в этом утверждении является то, что модель с экспоненциальной близостью не будет иметь ускорения, даже если разрешено изменение алфавита (для моделей с дискретной памятью, в которой хранятся символы). Однако Риган не доказал ни одной общей теоремы такого рода. Хюне ^[6] доказали, что если мы требуем, чтобы ускорение было получено с помощью онлайн-симуляции (что относится к ускорению на обычных машинах Тьюринга), то линейного ускорения не существует на машинах с древовидным хранилищем .

Ссылки

^ Перейти обратно: ^а ^б Христос Пападимитриу (1994). «2.4. Линейное ускорение». Вычислительная сложность . Аддисон-Уэсли.
^ Томас А. Судкамп (1994). «14.2 Линейное ускорение». Языки и машины: введение в теорию информатики . Аддисон-Уэсли.
^ Перейти обратно: ^а ^б Уинер, К.; Вексунг, Г. (1986). Вычислительная сложность . Спрингер. ISBN 978-9027721464 .
^ Гефферт, Вильям (1993). «Теорема ускорения без сжатия ленты» . Теоретическая информатика . 118 (1): 49–65. дои : 10.1016/0304-3975(93)90362-W .
^ Риган, Кеннет В. (1996). «Линейное время и вычисления с эффективным использованием памяти». SIAM Journal по вычислительной технике . 25 (1): 133–168.
^ Хюне, Мартин (1993). «Линейное ускорение не поддерживается на машинах Тьюринга с древовидным хранилищем». Письма об обработке информации . 47 (6): 313–318. дои : 10.1016/0020-0190(93)90078-Н .

[papadi-1] Перейти обратно: ^а ^б Христос Пападимитриу (1994). «2.4. Линейное ускорение». Вычислительная сложность . Аддисон-Уэсли.

[sudkamp-2] Томас А. Судкамп (1994). «14.2 Линейное ускорение». Языки и машины: введение в теорию информатики . Аддисон-Уэсли.

[WW-3] Перейти обратно: ^а ^б Уинер, К.; Вексунг, Г. (1986). Вычислительная сложность . Спрингер. ISBN 978-9027721464 .

[4] Гефферт, Вильям (1993). «Теорема ускорения без сжатия ленты» . Теоретическая информатика . 118 (1): 49–65. дои : 10.1016/0304-3975(93)90362-W .

[5] Риган, Кеннет В. (1996). «Линейное время и вычисления с эффективным использованием памяти». SIAM Journal по вычислительной технике . 25 (1): 133–168.

[6] Хюне, Мартин (1993). «Линейное ускорение не поддерживается на машинах Тьюринга с древовидным хранилищем». Письма об обработке информации . 47 (6): 313–318. дои : 10.1016/0020-0190(93)90078-Н .

[1]

[2]

[3]

[4]

[5]

[6]