Věta o lineárním zrychlení - Linear speedup theorem

v teorie výpočetní složitosti, věta o lineárním zrychlení pro Turingovy stroje uvádí, že vzhledem k jakékoli skutečné c> 0 a jakékoli k-tape Turingův stroj vyřeší problém včas f (n), existuje další k- páskový stroj, který řeší nanejvýš stejný problém včas f (n) / c + 2n + 3, kde k> 1 .^[1][2]Pokud je původní stroj nedeterministický, pak je nový stroj také nedeterministický. Konkrétní konstanty 2 a 3 v 2n + 3 lze snížit například na n + 2.^[1]

Důkaz

Konstrukce je založena na zabalení několika páskových symbolů původního stroje M do jednoho páskového symbolu nového stroje NMá podobný efekt jako používání delších slov a příkazů v procesorech: Zrychluje výpočty, ale zvětšuje velikost stroje. Kolik starých symbolů je zabaleno do nového symbolu, závisí na požadovaném zrychlení.

Předpokládejme, že nový stroj zabalí tři staré symboly do nového symbolu. Potom bude abeceda nového stroje ${ displaystyle Sigma cup Sigma ^ {3}}$: Skládá se z původních symbolů a zabalených symbolů. Nový stroj má stejné číslo k> 1 stavů pásky N skládá se z následujících komponent:

• stav `` M``;
• pro každou pásku: tři zabalené symboly, které popisují zabalený symbol pod hlavou, zabalený symbol vlevo a zabalený symbol vpravo; a
• pro každou pásku: původní poloha hlavy uvnitř zabaleného symbolu pod hlavou N.

Nový stroj N začíná kódováním daného vstupu do nové abecedy (proto musí obsahovat i jeho abecedu ${ displaystyle Sigma}$). Například pokud je vstup na 2-pásku M je vlevo, poté po kódování konfigurace pásky z N je na pravé straně:

[ #

_

A

b

b

A

b

b

A

_

...]

[ #

(_,_,_)

(_,_,_)

(_,_,_)

...]

[ #

_

_

_

_

_

_

_

_

_

...]

[ #

(_, a, b)

(b, a, b)

(b, a, _)

...]

Nový stroj obsahuje tři staré symboly (např. Prázdný symbol) _, symbol Aa symbol b) do nového symbolu ((_, a, b)) a zkopíruje ji na druhou pásku, přičemž první pásku smaže. Na konci inicializace nový stroj nasměruje hlavu na začátek. Celkově to trvá 2n + 3 kroky.

Po inicializaci stav N je ${ displaystyle (q_ {0}; ~~~?, ( _, _, _),?; ~~~?, ( _, a, b),?; ~~~ [1,1 ])}$, kde je symbol ${ displaystyle?}$ znamená, že jej stroj vyplní později; symbol ${ displaystyle [1,1]}$ znamená, že hlava původního stroje ukazuje na první symboly uvnitř ${ displaystyle ( _, _, _)}$ a ${ displaystyle ( _, a, b)}$. Nyní stroj začne simulovat m = 3 přechody M pomocí šesti vlastních přechodů (v tomto konkrétním případě nedojde k žádnému zrychlení, ale obecně m může být mnohem větší než šest). Nechte konfigurace M a N být:

[ #

_

_

b

b

A

b

b

A

_

...]

[ #

(_, a, b)

(b, a, b)

(b,_,_)

...]

[ #

_

A

b

b

A

b

b

_

_

...]

[ #

(_,_,b)

(b, a, b)

(b, a, _)

...]

kde tučně označené symboly označují polohu hlavy N je ${ displaystyle (q; ~~~?, ( _, _, b),?; ~~~?, (b, _, _),?; ~~~ [3,1])}$Nyní se stane toto:

• N pohybuje doprava, doleva, doleva, doprava. Po čtyřech tazích stroj N má všechny své ${ displaystyle?}$ naplněn a jeho stav se stane ${ displaystyle (q; ~~~ #, ( _, _, b), (b, a, b); ~~~ (b, a, b), (b, _, _) , ( _, _, _); ~~~ [3,1])}$
• Nyní N aktualizuje své symboly a stav podle m = 3 přechody původního stroje. To může vyžadovat dva tahy (aktualizovat aktuální symbol a aktualizovat jeden z jeho sousedních symbolů). Předpokládejme, že se původní stroj pohybuje takto (s odpovídající konfigurací N napravo):

[ #

_

_

_

_

_

b

b

A

_

...]

[ #

(_, a, b)

(b,_,_)

(_,_,_)

...]

[ #

_

A

b

b

_

_

_

_

_

...]

[ #

(_,_,_)

(_,_,b)

(b, a, _)

...]

Tedy stav N se stává ${ displaystyle (q '; ~~~?, ( _, _, b),?; ~~~?, (b, _, _),?; ~~~ [3,1]) }$.

Složitost

Inicializace vyžaduje 2n + 3 kroky. V simulaci 6 kroků N simulovat m kroky M. Výběr m> 6c produkuje provozní dobu ${ displaystyle leq f (n) / c + 2n + 3}$.

Reference