Złożoność obliczeniowa algorytmów
Maszyny Turinga
Kordian A. Smoliński
Uniwersytet A
ódzki, Wydział Fizyki i Informatyki Stosowanej
2007/2008
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 1 / 50
Maszyny Turinga (wykład 1)
1
Podstawy maszyn Turinga
2
Maszyny Turinga jako algorytmy
3
Maszyny Turinga z wieloma taśmami
4
Liniowe przyśpieszanie
5
Ograniczenia pamięciowe
6
Maszyny o dostępie swobodnym (RAM)
7
Maszyny niedeterministyczne
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 2 / 50
Podstawy maszyn Turinga
Podstawy maszyn Turinga
Definicja
Maszyna Turinga jest uporządkowaną czwórką M = (K, Ł, �, s), gdzie
K  skończony zbiór stanów, s " K  stan początkowy, Ł  skończony
zbiór symboli (Ł jest alfabetem M ), K )" Ł = ". Ł zawsze zawiera symbol
pusty i symbol końcowy . �  funkcja przejścia odwzorowująca K � Ł
w (K *" {h,  tak ,  nie }) � Ł � {�!, , -}. Stany: h (stan końcowy),
 tak (stan akceptujący),  nie (stan odrzucający) i kierunki ruchu
kursora: �! (w lewo) (w prawo) i - (pozostanie w miejscu) nie należą
do K *" Ł.
Ł" oznacza zbiór skończonych ciągów nad alfabetem Ł.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 3 / 50
Podstawy maszyn Turinga
Funkcja � jest programem maszyny. Dla każdej kombinacji stanu
i symbolu określa kolejny stan, symbol zastępujący symbol na taśmie
i kierunek przesunięcia kursora:
�
K � Ł (q, �) (p, �, D) " K � Ł � {�!, , -} .
Jeżeli dla q i p �(q, ) = (p, �, D), to � = i D =.
Początkowym stanem maszyny Turinga jest s, kursor wskazuje na pierwszy
symbol słowa wejściowego (danej) x " (Ł \ { })", którym musi być .
Maszyna zgodnie z funkcją � zmienia stan, zapisuje symbol i przesuwa
kursor. Po czym wykonuje kolejny krok. . .
Kursor nie ma możliwości przesunięcia się poza lewy koniec słowa
wejściowego. Jeżeli kursor przesuwa się poza prawy koniec słowa
wejściowego, przyjmujemy, że czyta symbol .
Maszyna zatrzymuje się w przypadku osiągnięcia trzech stanów: h,  tak
lub  nie . Jeżeli stanem jest  tak , to mówimy, że maszyna akceptuje
słowo wejściowe, jeżeli  nie  to, że je odrzuca.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 4 / 50
Podstawy maszyn Turinga
Jeżeli maszyna zatrzymuje się na słowie wejściowym x, to jako wynik
(słowo wyjściowe) maszyny M (x) uważamy:
 tak jeżeli maszyna zaakceptowała x;
 nie jeżeli maszyna odrzuciła x;
y jeżeli osiągnęła stan h, gdzie y jest słowem zapisanym na
taśmie maszyny w chwili zatrzymania, y " (Ł \ { })"
i rozpoczyna się od (na końcu może być ciąg symboli ).
Jeżeli M nie kończy obliczeń na słowie x, to piszemy M (x) = .
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 5 / 50
Podstawy maszyn Turinga
Przykład
M = (K, Ł, �, s), gdzie K = {s, p, q, r}, Ł = {0, 1, , }, � w tabeli, x = 010
(s, 010) (s, 010)
Tablica: �
(s, 010) (s, 010)
(s,0) (s, 0, ) (q,0) (s, 0, �!) (s, 010 ) (p, 010 )
(s,1) (s, 1, ) (q,1) (s, 0, �!) (q, 01 ) (s, 01 0)
(s, ) (p, , �!) (q, ) (s, 0, �!) (p, 01 0) (r, 0 0)
(s, ) (s, , ) (q, ) (h, , ) (s, 0 10) (p, 0 10)
(p,0) (q, , ) (r,0) (s, 1, �!) (q, 10) (s, 010)
(p,1) (r, , ) (r,1) (s, 1, �!) (p, 010) (h, 010)
(p, ) (p, , -) (r, ) (s, 1, �!)
Rysunek: Obliczenie
(p, ) (h, , ) (r, ) (h, , )
maszyny Turinga
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 6 / 50
Podstawy maszyn Turinga
Konfiguracja maszyny Turinga M jest trójką (q, w, u) " K � Ł" � Ł",
gdzie q jest bieżącym stanem M , w jest słowem na taśmie na lewo od
kursora wraz z symbolem wskazywanym przez kursor, u jest słowem na
prawo od kursora (być może pustym).
(s, , 010) (s, 0, 10) (s, 01, 0) (s, 010, ) (s, 010 , ) (p, 010, )
(q, 01 , ) (s, 01 , 0) (p, 01, 0) (r, 0 , 0) (s, 0 , 10)
(p, 0, 10) (q, , 10) (s, , 010) (p, , 010) (h, , 010)
Rysunek: Konfiguracje maszyny Turinga z poprzedniego przykładu
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 7 / 50
Podstawy maszyn Turinga
Definicja
Maszyna Turinga M z (q, w, u) przechodzi w jednym kroku do (q , w , u ):
M
(q, w, u) (q , w , u ), jeżeli dla � będącego ostatnim symbolem w,
i �(q, �) = (p, �, D), zachodzi q = p oraz dla
D = w jest w z � zamiast ostatniego � i dołączonym pierwszym
symbolem u (jeżeli u = , dołączamy ); u jest u bez
pierwszego symbolu ( pozostaje );
D =�! w jest w bez �; u jest u poprzedzonym przez �;
D = - w jest w z � zamiast �, u jest u.
M z (q, w, u) przechodzi w k krokach do (q , w , u ):
k
M
(q, w, u) (q , w , u ), gdzie k " N, jeżeli istnieją konfiguracje (qi, wi, ui),
M
i = 0, . . . , k, takie, że (qi, wi, ui) (qi+1, wi+1, ui+1), przy czym
(q0, w0, u0) = (q, w, u) oraz (qk, wk, uk) = (q , w , u ).
"
M
M z (q, w, u) przechodzi do (q , w , u ): (q, w, u) (q , w , u ), jeżeli
k
M
"k " N: (q, w, u) (q , w , u ).
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 8 / 50
Podstawy maszyn Turinga
Przykład (Maszyna Turinga obliczająca następnik dla liczb binarnych)
K = {s, q}, Ł = {0, 1, , }
(s, , 11011) (s, 1, 1011) (s, 11, 011)
(s, 110, 11) (s, 1101, 1) (s, 11011, )
(s, 11011 , ) (q, 11011, )
p " K � " Ł �(p, �)
(q, 1101, 0 ) (q, 110, 00 )
s 0 (s, 0, ) (h, 111, 00 )
s 1 (s, 1, )
Rysunek: Obliczenie na wejściu 11011
s (q, , �!)
s (s, , )
q 0 (h, 1, -)
q 1 (q, 0, �!)
(s, , 111) (s, 1, 11) (s, 11, 1)
q (q, , )
(s, 111, ) (s, 111 , ) (q, 111, )
(q, 11, 0 ) (q, 1, 00 ) (q, , 000 )
(h, 0, 00 )
Rysunek: Obliczenie na wejściu 111
Dla słowa 1k następuje przepełnienie  błąd można naprawić stosując maszynę
z poprzedniego przykładu jako  podprogram przesuwający słowo wejściowe
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 9 / 50
o jeden w prawo i dopisujący początkowe zero. Maszyna realizująca taki program
Podstawy maszyn Turinga
Przykład (Maszyna Turinga dla palindromów)
(s, , 0010)
(s, 0, 010)
(q0, 0, 10)
(q0, 01, 0)
(q0, 010, )
(q0, 010 , )
(p0, 010, )
(r, 01, )
(r, 0, 1 )
(r, , 01 )
(s, , 1 )
s 0 (q0, , )
(q0, 1, )
p0 0 (r, , )
s 1 (q1, , )
(q0, 1 , )
p0 1 ( nie , 1, -)
s (s, , )
(p0, 1, )
p0 ( tak , , )
s ( tak , , -)
( nie , 1, )
p1 0 ( nie , , -)
q0 Kordian A. Smoliński0, )
0 (q0,
(UA
) Złożoność obliczeniowa 2007/2008 10 / 50
p1 1 (ralgorytmów Rysunek: Obliczenie
, , �!)
q0 1 (q0, 1, )
dla 0010
p ( tak )
Maszyny Turinga jako algorytmy
Maszyny Turinga jako algorytmy
Maszyny Turinga nadają się do:
obliczania funkcji na słowach
rozpoznawania i rozstrzygania języków
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 11 / 50
Maszyny Turinga jako algorytmy
Definicja
Niech L �" (Ł \ { })"  język, a M  maszyna Turinga, taka że
"x " (Ł \ { })" :
(x " L =�! M (x) =  tak ) '" (x " L =�! M (x) =  nie ) .
Mówimy wówczas, że M rozstrzyga L. Jeżeli język L jest rozstrzygany
przez pewną maszynę Turinga M , to L nazywamy językiem rekurencyjnym.
Maszyna M rozpoznaje język L, jeżeli
"x " (Ł \ { })" :
(x " L =�! M (x) =  tak ) '" (x " L =�! M (x) = ) .
Jeżeli język L jest rozpoznawany przez pewną maszynę Turinga M , to L
nazywamy językiem rekurencyjnie przeliczalnym.
Rozpoznawanie nie jest prawdziwym problemem algorytmicznym a jedynie
użytecznym sposobem klasyfikacji problemów.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 12 / 50
Maszyny Turinga jako algorytmy
Stwierdzenie
Jeżeli język L jest rekurencyjny, to jest rekurencyjnie przeliczalny.
Dowód.

L jest rekurencyjny, więc istnieje M , króra rozstrzyga L. Zbudujemy M , która

rozpoznaje L: niech M zachowuje się tak jak M , z wyjątkiem sytuacji, gdy M ma

zatrzymać się i przejść do  nie , wówczas M przesuwa się w prawo i nigdy nie
zatrzymuje.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 13 / 50
Maszyny Turinga jako algorytmy
Definicja
Niech f : (Ł \ { })" Ł" i M jest maszyną Turinga z alfabetem Ł.
Mówimy, że M oblicza f , jeżeli
"x " (Ł \ { })" : M (x) = f (x) .
Jeżeli dla funkcji f istnieje obliczająca ją maszyna Turinga, to f nazywamy
funkcją rekurencyjną.
Funkcja f : {0, 1}" {0, 1, }" taka, że f (x) = x, jest rekurencyjna
(obliczana przez maszynę z pierwszego przykładu). Funkcja
s : {0, 1}" {0, 1, }" taka, że s(x) jest reprezentacją binarną n + 1, gdy
x jest reprezentacją binarną dotatniej liczby całkowitej n jest rekurencyjna.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 14 / 50
Maszyny Turinga jako algorytmy
Musimy zdecydować, w jaki sposób będziemy zapisywać problem za
pomocą słowa. Po ustaleniu reprezentacji, algorytm dla problemu
decyzyjnego jest maszyną Turinga rozstrzygającą odpowiedni język. Dla
problemów wymagających bardziej złożonej odpowiedzi, maszyna Turinga
oblicza odpowiednią funkcję na słowach.
Dowolny  skończony obiekt matematyczny może być zapisany w postaci
skończonego słowa nad odpowiednim alfabetem: np. elementy zbioru skończonego
(wierzchołki grafu) jako liczby binarne, pary i k-krotki prostszych obiektów
zapisujemy z użyciem nawiasów i przecinków, zbiory skończone złożone
z prostszych obiektów reprezentujemy z użyciem nawiasów klamrowych itd. Graf
może być też reprezentowany przez macierz sąsiedztwa, którą można zapisać jako
słowo złożone z wierszy oddzielonych symbolem  ; .
Liczby całkowite, zbiory skończone, grafy i inne obiekty elementarne mogą
być zapisane na wiele sposobów, mogących się różnić formą i długością.
Wszystkie dopuszczalne kodowania są wielomianowo równoważne. Dla
maszyny Turinga, rozwiązującej konkretny program obliczeniowy,
zakładamy, że używamy zwięzłej reprezentacji danych wejściowych. Liczby
będziemy zawsze reprezentować binarnie.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 15 / 50
Maszyny Turinga z wieloma taśmami
Maszyny Turinga z wieloma taśmami
Definicja
Maszyna Turinga z k taśmami (k d" 0) jest czwórką M = (K, Ł, �, s),
gdzie K, Ł i s mają takie same znaczenie jak dla zwykłej maszyny
Turinga, a � : K � Łk (K *" {h,  tak ,  nie }) � (Ł � {�!, , -})k jest
programem określającym kolejny stan maszyny, pisane symbole i kierunki
ruchu taśm na podstawie bieżącego stanu maszyny i czytanych symboli na
wszystkich taśmach.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 16 / 50
Maszyny Turinga z wieloma taśmami
Przykład (Maszyna Turinga o dwóch taśmach dla palindromów)
p " K �1 " Ł �2 " Ł �(p, �1, �2)
s 0 (s, 0, , 0, )
s 1 (s, 1, , 1, )
s (s, , , , )
s (q, , �!, , -)
q 0 (q, 0, �!, , -)
q 1 (q, 1, �!, , -)
q (p, , , , �!)
p 0 0 (p, 0, , , �!)
p 1 1 (p, 1, , , �!)
p 0 1 ( nie , 0, -, 1, -)
p 1 0 ( nie , 1, -, 0, -)
p ( tak , , -, , )
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 17 / 50
Maszyny Turinga z wieloma taśmami
Konfiguracja maszyny Turinga z k taśmami jest to (2k + 1)-krotka
(q, w1, u1, . . . , wk, uk), gdzie q jest bieżącym stanem, wiui słowem na i-tej
taśmie, a i-ty kursor wskazuje na ostatni symbol wi.

M z (q, w1, u1, . . . , wk, uk) przechodzi do (q, w1, u1, . . . , wk, uk):
M

(q, w1, u1, . . . , wk, uk) (q, w1, u1, . . . , wk, uk) ,
jeżeli dla �i będącego ostatnim symbolem wi (i = 1, . . . , k)
i �(q, �1, . . . , �k) = (p, �1, . . . , �k, D1, . . . , Dk) zachodzą dla każdego
i = 1, . . . , k takie warunki jak dla zwykłej maszyny Turinga. Analogicznie
definiujemy przechodzenie w n krokach.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 18 / 50
Maszyny Turinga z wieloma taśmami
Maszyna z k taśmami rozpoczyna obliczenia w konfiguracji
(s, , x, , , . . . , , ).
"
M
M (x) =  tak jeżeli (s, , x, , , . . . , , ) ( tak , w1, u1, . . . , wk, uk)
M"
M (x) =  nie jeżeli (s, , x, , , . . . , , ) ( nie , w1, u1, . . . , wk, uk)
"
M
M (x) = y jeżeli (s, , x, , , . . . , , ) (h, w1, u1, . . . , wk, uk),
i y = wkuk z usuniętymi początkowym i końcowymi
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 19 / 50
Maszyny Turinga z wieloma taśmami
Definicja
Jeżeli dla maszyny Turinga M z k taśmami i dla słowa wejściowego x
zachodzi relacja
t
M
(s, , x, , , . . . , , ) (H , w1, u1, . . . , wk, uk) ,
gdzie H " {h,  tak ,  nie }, to czas wymagany przez maszynę M dla x
wynosi t. Jeżeli M (x) = , to za czas wymagany przez M dla x
przyjmujemy ".
Maszyna M działa w czasie f (n), jeżeli dla dowolnego słowa wejściowego
x czas wymagany przez maszynę M jest równy co najwyżej f (|x|)
(|x|  długość słowa x).
Funkcja f (n) jest ograniczeniem czasowym dla M .
Niech L �" (Ł \ { })" będzie językiem rozstrzyganym przez maszynę
Turinga z wieloma taśmami działającą w czasie f (n). Mówimy wówczas,
że L " TIME(f (n)).
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 20 / 50
Maszyny Turinga z wieloma taśmami
TIME(f (n)) nazywamy klasą złożoności. Jest to zbiór języków
zawierający dokładnie te języki, które są rozstrzygane przez maszyny
Turinga z wieloma taśmami działające w czasie ograniczonym przez f (n).
Przykład
Liczba kroków potrzebnych maszynie Turinga (z jedną taśmą) do rozstrzygnięcia,
czy słowo długości n jest palindromem.
n
Maszyna działa w etapach: Najpierw, w 2n + 1 krokach porównuje pierwszy
2
i ostatni symbol. Procedurę powtarza ze słowem długości n - 2, póz
niej n - 4,
itd. Całkowita liczba kroków wynosi co najwyżej
(n+1)(n+2)
(2n + 1) + (2n - 3) + � � � = f (n) = . Język palindromów należy do
2
klasy TIME((n+1)(n+2) ). Istotne jest tylko to, że f (n) jest funkcją kwadratową
2
n, tj., że f (n) = O(n2).
Oszacowanie jest pesymistyczne  obliczając f (n) musimy wziąć pod uwagę
najgorszy przypadek danych wejściowych.
Dowolna maszyna Turinga z jedną taśmą rozstrzygająca palindromy musi mieć

&!(n2) czasu. Maszyna z dwiema taśmami potrzebuje czasu f (n) = 3n + 3, czyli
palindromy są w klasie TIME(3n + 3).
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 21 / 50
Maszyny Turinga z wieloma taśmami
Twierdzenie
Dla dowolnej maszyny Turinga z k taśmami działającej w czasie f (n)

można zbudować maszynę Turinga M działającą w czasie O(f (n)2), taką

że dla dowolnego słowa wejściowego x zachodzi M (x) = M (x).
Dowód.

Niech M = (K, Ł, �, s). Opiszemy M = (K , Ł , � , s). Pojedyncza taśma M musi

symulować k taśm M  na taśmie M przechowujemy konkatenację słów z taśm M ,
pamiętamy także pozycję każdego kursora i prawy koniec każdego ze słów.
Niech Ł = Ł *" Ł *" { , }, gdzie Ł = {� : � " Ł} jest zbiorem wersji symboli
z kursorem. jest wersją , przez którą można przejść w lewo, oznacza prawy koniec
słowa. Konfiguracja (q, w1, u1, . . . , wk, uk) jest symulowana przez

(q, , w1u1 w2u2 . . . wkuk ), wi oznacza wi z zastąpionym przez i ostatnim �i

zastąpionym przez �i; dwa oznaczają koniec słowa M .

Przed rozpoczęciem symulacji M przesuwa słowo wejściowe o jedne w prawo, wstawia
na początku , po słowie wejściowym dopisuje ( )k-1 (co można uczynić dodając

2k + 2 nowych stanów M ).
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 22 / 50
Maszyny Turinga z wieloma taśmami
Dowód (cd.)

M symuluje jeden krok M dwukrotnie czytając swoje słowo od lewej do prawej

i z powrotem. W pierwszym przebiegu M zbiera informacje o k symbolach
wskazywanych przez kursory, zapamiętuje je na nowych stanach, po jednym dla każdej
kombinacji stanu i k-krotki symboli M .

Na podstawie stanu w chwili zakończenia pierwszego przeglądu M zna zmiany w słowie

odzwierciedlające zmiany wykonywane przez M w trakcie symulowanego kroku. M
w drugim przeglądzie zatrzymuje się przy symbolach podkreślonych i modyfikuje jeden
lub dwa symbole w sąsiedztwie, aby poprawnie zakodować zapisanie symbolu i zmianę
pozycji kursora M . (Jeżeli kursor na prawym końcu jednego ze słów M przesuwa się
w prawo, to trzeba utworzyć miejsce na nowy symbol ( ): zmieniamy na
i przesuwamy kursor do prawego końca, a następnie przesuwamy wszystkie symbole o 1
w prawo, aż do włącznie, na jego pozycji piszemy ).

Symulację kontynuujemy aż do zatrzymania sie M . Wtedy M kasuje zawartość
wszystkich taśm M z wyjątkiem ostatniej i zatrzymuje się.
M zatrzymuje się w czasie f (|x|), czyli żadne z jej słów nie jest dłuższe niż f (|x|).

Zatem całkowita długość słowa na taśmie M nie przekracza k(f (|x|) + 1) + 1.
Symulacja jednego kroku wymaga najwyżej dwukrotnego przejścia tego słowa tam
i z powrotem, czyli 4k(f (|x|) + 1) + 4 ruchy plus najwyżej 3k(f (|x|) + 1) + 3 ruchów na
każdą taśmę symulowanej maszyny. Razem otrzymujemy O(k2f (|x|)2, czyli O(f (|x|)2),
gdyż k jest ustalone i niezależne od x.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 23 / 50
Maszyny Turinga z wieloma taśmami
Nie wymyślono żadnych  realnych ulepszeń maszyny Turinga, które
zwiększyłyby dziedzinę rozstrzyganych przez nie języków czy wpłynęły
bardziej niż wielomianowo na szybkość ich działania.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 24 / 50
Maszyny Turinga z wieloma taśmami
Maszyny Turinga (wykład 2)
1
Podstawy maszyn Turinga
2
Maszyny Turinga jako algorytmy
3
Maszyny Turinga z wieloma taśmami
4
Liniowe przyśpieszanie
5
Ograniczenia pamięciowe
6
Maszyny o dostępie swobodnym (RAM)
7
Maszyny niedeterministyczne
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 25 / 50
Liniowe przyśpieszanie
Liniowe przyśpieszanie
Twierdzenie

Niech L " TIME(f (n)). Wówczas " > 0 zachodzi L " TIME(f (n)),

gdzie f (n) = f (n) + n + 2.
Dowód.
M = (K, Ł, �, s) jest maszyną z k taśmami, rozstrzygającą L i działającą w czasie f (n).

Zbudujemy M = (K , Ł , � , s ) z k taśmami, działającą w czasie f (n) i symulującą

M . Liczba taśm k = k, gdy k > 1 i k = 2, gdy k = 1. Każdy symbol M koduje kilka

symboli M , stąd M symuluje kilka ruchów M w czasie jednego ruchu.

Niech m będzie liczbą całkowitą zależną jedynie od M i . Alfabet M prócz symboli M

zawiera m-krotki symboli M , tzn. Ł = Ł *" Łm. Początkowo M przesuwa kursor po 1.
taśmie w prawo, czytając x. Po przeczytaniu m symboli �1�2 . . . �n na 2. taśmie
dopisywany jest jeden symbol (�1, �2, . . . , �n) " Ł . Symbole zapamiętujemy w stanach

M , jest to możliwe po dodaniu do K stanów K � Łi dla i = 1, . . . , m - 1. Jeżeli
w trakcie budowania m-krotki natrafimy na koniec x, uzupełniamy krotkę dopisując

|x|
wymaganą liczbę . Po m + 2 krokach 2. taśma zawiera (za skrajnym lewym )
m
skompresowane słowo wejściowe. Pozostałe taśmy M (o ile były), zawierają .
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 26 / 50
Liniowe przyśpieszanie
Dowód (cd.).
Od teraz 2. taśmę traktujemy jako taśmę zawierającą wejście. Jeżeli k > 1, to 1. taśmę
traktujemy jako zwykłą taśmę roboczą (wpisujemy po słowie wejściowym). Wszystkie
k taśm będzie zawierało jedynie m-krotki symboli.

M symuluje m ruchów M w co najwyżej 6 swoich ruchach, taką symulację m kroków

M nazywamy etapem. Na początku etapu stan M zawiera (k + 1)-krotkę
(q, j1, . . . , jk), gdzie q jest stanem M na początku etapu oraz ji d" m jest pozycją i-tego
kursora wewnątrz aktualnie czytanej m-krotki. Jeżeli więc w pewnym momencie stan M
jest q, a i-ty kursor M jest l-tym symbolu (licząc od pierwszego ), to i + 1-szy
na
l
kursor M wskazuje na -ty symbol na prawo od , a stanem M jest (q, l mod m).
m

Następnie M przesuwa wszystkie kursory o jedną pozycję w prawo, potem o dwie

pozycje w prawo, następnie o jedną w lewo. W stanie M zapamiętane są wszystkie
symbole wskazywane przez kursory lub stojące tuż obok (dodajemy do K wszystkie

stany K � {1, . . . , m}k � Ł3mk). Na podstawie tej informacji M może w pełni
przewidzieć m kolejnych ruchów M . Istotnie, w m krokach żaden z kursorów M nie
wyjdzie poza obszar bieżącej m-krotki oraz m-krotek bezpośrednio z nią sąsiadujących.

Dalej M korzysta z � , aby w dwóch krokach dokonać zmian w zawartości taśm i ustalić

stan po m ruchach M . Symulacja m kroków M jest zakończona w 6 krokach M .

Po zaakceptowaniu lub odrzuceniu słowa wejściowego przez M , M zatrzymuje się

z takim samym wynikiem. Czas pracy maszyny M dla słowa x wynosi w najgorszym

f (|x|)
6
przypadku |x| + 2 + 6 . Wybierając m = otrzymujemy tezę.
m
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 27 / 50
Liniowe przyśpieszanie
Maszyny działające w czasie krótszym niż n, istnieją, ale nie są
interesujące, gdyż maszyna Turinga potrzebuje n kroków na przeczytanie
całego słowa wejściowego. Zatem każde  przyzwoite ograniczenie
czasowe spełnia zależność f (n) e" n. Jeżeli f (n) jest liniowa, np.
f (n) = cn dla stałej c > 1, to twierdzenie mówi, że można stałą c uczynić
dowolnie bliską 1. Jeżeli f (n) jest nadliniowa, wtedy stały czynnik
w najbardziej znaczącym wyrazie może być dowolnie zmniejszony, tzn.
ograniczenie czasowe może być dowolnie liniowo zmniejszone. Wyrazy
niższego rzędu mogą być całkowicie pominięte.
Każde wielomianowe ograniczenie czasowe może być reprezentowane przez
najbardziej znaczący wyraz. Jeżeli L jest językiem wielomianowo
rozstrzygalnym, to należy do klasy TIME(nk) dla pewnego k > 0.
Sumę wszystkich klas TIME(nk), czyli zbiór języków rozstrzygalnych
w czasie wielomianowym przez maszyny Turinga, oznaczamy przez P. Jest
to najważniejsza klasa złożoności obliczeniowej.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 28 / 50
Ograniczenia pamięciowe
Ograniczenia pamięciowe
Przyjm3
my, że pamięć używana przez maszynę M na x podczas obliczenia
"
k
M
(s, , x, . . . , , ) (H , w1, u1, . . . , wk, uk) jest równa |wiui|.
i=1
W oszacowaniu tym ukryty jest spory nadmiar.
Przykład
Czy można rozpoznawać palindromy w pamięci zdecydowanie mniejszej niż n?
Taśma 1. zawiera x i nigdy się nie zmienia. W i-tym etapie taśma 2. zawiera
zapisaną binarnie liczbę całkowitą i. Rozpoznajemy i zapamiętujemy i-ty symbol
x: wpisujemy do taśmy 3. j = 1 i porównujemy i z j przez przesuwanie kursorów
na taśmach: jeżeli j < i, zwiększamy j o 1 i przesuwamy kursor taśmy 1.
w prawo; jeżeli j = i, zapamiętujemy czytany symbol, ustalamy j = 1
i odnajdujemy i-ty od końca symbol x.
Jeżeli odnalezione symbole są różne  zatrzymujemy w  nie ; jeżeli równe,
zwiększamy i o 1 i rozpoczynamy kolejny etap. Jeżeli podczas pewnego etapu
i-tym symbolem x będzie  zatrzymujemy w stanie  tak .
Używana pamięć wynosi O(log n). Maszyna tylko odczytuje x. Słowa na
pozostałych taśmach są nie dłuższe niż log n + 1.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 29 / 50
Ograniczenia pamięciowe
Niech k > 2 i k " N. Maszyna Turinga z k taśmami oraz wejściem
i wyjściem jest maszyną Turinga z k taśmami, której program � spełnia
następujący warunek: jeżeli �(q, �1, . . . , �k) = (p, �1, D1, . . . , �k, Dk), to
�1 = �1 i Dk =�!, a ponadto jeżeli � = , to D1 =�!.

Stwierdzenie
Dla dowolnej maszyny Turinga M działającej w czasie ograniczonym przez

f (n) istnieje maszyna Turinga M o k + 2 taśmach z wyróżnionym
wejściem i wyjściem, działająca w czasie O(f (n)).
Dowód.

M rozpoczyna pracę od przekopiowania wejścia na taśmę 2., a następnie symuluje pracę

M o k taśmach na taśmach o numerach od 2 do k + 1. Gdy M się zatrzymuje, M
kopiuje wynik na taśmę k + 2. i zatrzymuje się.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 30 / 50
Ograniczenia pamięciowe
Definicja
Niech dla maszyny Turinga z k taśmami i słowa wejściowego x zachodzi
"
M
(s, , x, . . . , , ) (H , w1, u1, . . . , wk, uk), gdzie H " {h,  tak ,  nie }
jest stanem końcowym. Pamięcią wymaganą przez maszynę M dla słowa
k
wejściowego x jest |wiui|. Jeżeli M jest maszyną z wyróżnionym
i=1
wejściem i wyjściem, to pamięć wymagana przez maszynę M dla słowa
k-1
wejściowego x jest |wiui|. Niech f : N N. Mówimy, że maszyna
i=2
Turinga działa w pamięci ograniczonej przez f (n), jeżeli dla dowolnego
słowa wejściowego x M potrzebuje najwyżej pamięci f (|x|).
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 31 / 50
Ograniczenia pamięciowe
Definicja
Niech L będzie językiem. Mówimy, że L należy do klasy złożoności
pamięciowej SPACE(f (n)), jeżeli istnieje maszyna Turinga
z wyróżnionym wejściem i wyjściem, która rozstrzyga L i działa w pamięci
ograniczonej przez f (n).
Palindromy należą do klasy SPACE(log n). Ta ważna klasa jest
oznaczana przez L.
Twierdzenie
Niech L będzie językiem z klasy SPACE(f (n)). Wtedy dla dowolnego
> 0 zachodzi L " SPACE(2 + f (n)).
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 32 / 50
Maszyny o dostępie swobodnym (RAM)
Maszyny o dostępie swobodnym (RAM)
Czy maszyny Turinga mogą służyć do implementacji dowolnych
algorytmów?
Twierdzimy, że tak. Nieformalne twierdzenie, znane jako teza Churcha,
stanowi, że każdy algorytm może być przedstawiony jako maszyna Turinga.
Każda sensowna próba stworzenia matematycznego modelu obliczeń
komputerowych i zdefiniowania czasu jego działania musi doprowadzić do
modelu obliczeń i związanej z nim miary kosztu czasowego, które są
wielomianowo równoważne maszynom Turinga.
Zdefiniujemy model obliczeń oddający wiele cech współczesnych
algorytmów komputerowych i pokażemy, że jest on wielomianowo
równoważny maszynie Turinga.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 33 / 50
Maszyny o dostępie swobodnym (RAM)
Maszyna o dostępie swobodnym (RAM1) jest urządzeniem liczącym
składającym się z programu operującego na jednej strukturze
danych  tablicy rejestrów. Każdy z rejestrów może przechowywać
dowolnie dużą liczbę całkowitą. Instrukcje RAM przypominają instrukcje
prawdziwych komputerów:
Instrukcje RAM
READ j r0 �! ij
r0
HALF r0 �!
2
READ "j r0 �! ir
j
JUMP j � �! j
STORE j rj �! r0
JPOS j if r0 > 0 then � �! j
STORE "j rr �! r0
j
JZERO j if r0 = 0 then � �! j
LOAD x r0 �! x
JNEG j if r0 < 0 then � �! j
ADD x r0 �! r0 + x
HALT � �! 0
SUB x r0 �! r0 - x
j  liczba całkowita; rj  zawartość rejestru j; ij  i-ty element wejścia;
x  argument postaci j, "j lub = j. Wartość j wynosi rj, "j  rr , = j  j.
j
�  licznik rozkazów. Każda instrukcja, dla której jawnie nie zaznaczono zmiany
�, powoduje � �! � + 1.
1
Random Access Machine.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 34 / 50
Maszyny o dostępie swobodnym (RAM)
Formalnie, program RAM jest skończonym ciągiem instrukcji
 = (Ą1, Ą2, . . . , Ąm), gdzie każda z instrukcji Ąi jest jedną z podanych.
W każdej chwili obliczeń rejestr i (i e" 0) zawiera liczbę całkowitą,
oznaczaną przez ri. W każdym momencie obliczeń wykonywana jest
instrukcja Ą�, gdzie liczba � jest  licznikiem programu . Wykonanie
instrukcji może dać w wyniku zmianę wartości jednego z rejestrów i zmianę
�. Semantyka (znaczenie) instrukcji jest zbliżona do asemblera.
Rejstr 0 jest akumulatorem, w którym wykonuje się obliczenia. Maszyna
RAM ma trzy tryby adresowania: argumenty mogą być: w rejestrze j (j),
w rejestrze, którego numer znajduje się w rejestrze j ("j) lub samą liczbą j
(= j).
Instrukcja powoduje także zmianę �. O ile nie jest to jedna z instrukcji
skoku lub HALT, to � jest zwiększane o 1. HALT powoduje zatrzymanie
obliczeń, przyjmujemy, że dowolna semantycznie niepoprawna instrukcja
jest równoważna HALT. Początkowo rejestry zawierają 0. Dane programu
RAM to skończony ciąg liczb całkowitych zawartych w skończonej tablicy
rejestrów danych, I = (i1, . . . , in). W chwili zakończenia pracy poprawny
wynik znajduje się w akumulatorze.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 35 / 50
Maszyny o dostępie swobodnym (RAM)
RAM realizuje Ą1 i wykonuje dyktowane przez nią zmiany. Następnie
realizuje Ą�, gdzie � jest nową wartością licznika programu, itd., aż do
zatrzymania. Obliczenia RAM można sformalizować, używając pojęcia
konfiguracji maszyny RAM  pary C = (�, R), gdzie � jest instrukcją,
która ma być wykonana, a R = {(j1, rj1), (j2, rj2), . . . , (jk, rjk)} jest
skończonym zbiorem par rejestr-wartość. R opisuje tylko te rejestry,
w których jest niezerowa wartość. Początkową konfiguracją jest więc (1, ").

Ustalmy program  oraz dane I . Niech C = (�, R) i C = (� , R ) będą

konfiguracjami. RAM przechodzi w jednym kroku z C do C ,
,I
(�, R) (� , R ), jeżeli � jest nową wartością � po wykonaniu Ą�  �-tej
instrukcji programu  oraz R = R, jeżeli Ą� było instrukcją skoku lub
HALT, albo R powstaje z R przez przez zastąpienie pary (j, x) parą (j, x )
k
,I
obliczoną zgodnie z treścią instrukcji Ą�. Przechodzenie w k krokach
"
,I
i przechodzenie definiujemy przez analogię.
Niech   program RAM, D  zbiór skończonych ciągów liczb
całkowitych i Ć funkcja całkowitoliczbowa na D.  oblicza Ć, jeżeli dla
"
,I
dowolnego I " D zachodzi (1, ") (0, R), gdzie (0, Ć(I )) " R.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 36 / 50
Maszyny o dostępie swobodnym (RAM)
Określając wymagania czasowe dla programów RAM, przyjmujemy
założenie, że liczymy każdą operację jako pojedynczy krok.
Niech b(i) będzie binarną reprezentacją liczby całkowitej i bez zer
wiodących i ze znakiem  - , jeżeli i < 0. Długością liczby całkowitej i
jest (i) = |b(i)|. Jeżeli I = (i1, . . . , ik) jest ciągiem liczb, to jego długość
k
wynosi (I ) = (ij).
j=1
Niech program  RAM oblicza funkcję całkowitoliczbową Ć na D. Niech f
będzie funkcją określoną na liczbach naturalnych o wartościach
k
,I
naturalnych i niech dla dowolnego I " D zachodzi (1, ") (0, R), gdzie
k d" f ( (I )). Mówimy, że  oblicza Ć w czasie f (n).
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 37 / 50
Maszyny o dostępie swobodnym (RAM)
Dowolna maszyna Turinga może być symulowana przez program RAM.
Niech Ł = {�1, . . . , �k} będzie alfabetem maszyny Turinga. Niech DŁ
będzie zbiorem skończonych ciągów liczb całkowitych:
DŁ = {(i1, . . . , in, 0): n e" 0, 1 d" ij d" k, j = 1, . . . , n}. Jeżeli
L " (Ł \ { })" jest językiem, to definiujemy na DŁ funkcję ĆL
o wartościach w {0, 1} taką, że ĆL(i1, . . . , in, 0) = 1, jeżeli
�i1, . . . , �in " L, i 0 w przeciwnym razie.
Twierdzenie
Jeżeli L jest językiem należącym do TIME(f (n)), to istnieje program
RAM obliczający ĆL w czasie O(f (n)).
Dowód.
Niech M = (K, Ł, �, s)  maszyna Turinga rozstrzygająca L w czasie f (n). Program
RAM rozpoczyna od skopiowania danych do rejestrów o numerach od 4 do n + 3.
Rejestr 1 zawiera 4  będzie wskazywał na rejestr zawierający symbol pod kursorem.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 38 / 50
Maszyny o dostępie swobodnym (RAM)
Dowód (cd.).
Następnie symulujemy działanie maszyny Turinga krok po kroku. Program ma ciąg
instrukcji symulujący działanie każdego stanu q " K. Ciąg ten składa się z k podciągów,
gdzie k = |Ł|. Niech j-ty podciąg rozpoczyna się od instrukcji o numerze Nq,�j .
Przypuśćmy, że �(q, �j) = (p, �l, D). Wówczas instrukcje j-tego podciągu są
następujące:
Nq,�j LOAD "1 pobierz symbol wskazywany przez kursor
Nq,�j + 1 SUB = j odejm3
j  numer badanego symbolu
Nq,�j + 2 JZERO Nq,�j + 4 jeżeli symbolem jest �j , to trzeba coś wykonać
Nq,�j + 3 JUMP Nq,�j+1 w przeciwnym razie przejdz
do następnego symbolu
Nq,�j + 4 LOAD l �l jest właśnie zapisanym symbolem
Nq,�j + 5 STORE "1 zapisz �l
Nq,�j + 6 LOAD 1 pozycja kursora
Nq,�j + 7 ADD = d d jest 1 dla D =, -1 dla D =�! i 0 dla D = -
Nq,�j + 8 STORE 1
Nq,�j + 9 JUMP Np,�1 rozpoczn3
symulację stanu p
Stany  tak i  nie są symulowane przez proste sekwencje instrukcji RAM, pobierające
odpowiednio stałą 1 lub 0 do akumulatora, a następnie wykonujące HATL.
Czas konieczny do wykonania instrukcji symulujących pojedynczy ruch jest stały (zależny
od M ). Dodatkowo potrzeba jedynie O(n) instrukcji na przekopiowanie danych.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 39 / 50
Maszyny o dostępie swobodnym (RAM)
Lemat
Po t krokach obliczeń programu RAM na danych I zawartość każdego
rejestru ma długość najwyżej t + (I ) + (B), gdzie B jest największą
liczbą całkowitą zapisaną jawnie w instrukcji programu .
Dowód.
Przez indukcję względem t. Teza jest prawdziwa przed wykonaniem pierwszego kroku,
gdy t = 0. Załóżmy jej prawdziwość aż do wykonania kroku t. Może zajść kilka
przypadków. Jeżeli wykonywana instrukcja jest instrukcją skoku lub zatrzymania, to
zawartość żadnego rejestru się nie zmienia. Jeżeli jest to LOAD lub STORE, to
zawartość modyfikowanych rejestrów pochodzi z innych rejestrów, była więc w nich
w poprzednim kroku obliczeń, więc teza zachodzi. Jeżeli instrukcją jest READ, to wyraz
(I ) z ograniczenia gwarantuje zachodzenie tezy. Jeżeli instrukcja jest instrukcją
arytmetyczną, to wykonuje ona działanie na dwóch liczbach i i j, z których każda jest
albo zawarta w rejestrze w poprzednim kroku, albo zapisana w programie , więc w tym
przypadku nie większa niż B. Długość wyniku może być co najwyżej o 1 większa niż
długość najdłuższego argumentu, który z założenia indukcyjnego jest nie dłuższy niż
t - 1 + (I ) + (B). Zatem i w tym przypadku zachodzi teza.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 40 / 50
Maszyny o dostępie swobodnym (RAM)
Dowolna maszyna RAM może być symulowana przez maszynę Turinga
jedynie z wielomianową utratą efektywności. Załóżmy, że Ć jest funkcją
określoną na D o wartościach całkowitych, gdzie D jest zbiorem
skończonych ciągów liczb całkowitych. Binarna reprezentacja ciągu
I = (i1, . . . , in), oznaczana b(I ) jest słowem b(i1); . . . ; b(in). Mówimy, że
maszyna Turinga M oblicza Ć, jeżeli dla dowolnego I " D zachodzi
M (b(I )) = b(Ć(I )).
Twierdzenie
Jeżeli program  maszyny RAM oblicza funkcję Ć w czasie f (n), to
istnieje maszyna Turinga M z 7 taśmami, obliczająca Ć w czasie O(f (n)3).
Dowód.
1. taśma M jest taśmą wejściową tylko do odczytu. 2. taśma zawiera reprezentację
zawartości rejestrów R i składa się z sekwencji słów postaci b(i) : b(ri) oddzielonych  ;
oraz, ewentualnie, ciągami znaków pustych. Całość kończymy specjalnym znakiem, np.
. Za każdym razem, gdy uaktualniana jest zawartość rejestru i, poprzednia para jest
kasowana (zapisujemy w to miejsce ciąg ), a nowa para jest dopisywana na końcu
słowa.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 41 / 50
Maszyny o dostępie swobodnym (RAM)
Dowód (cd.).
Stany M dzielimy na m grup, gdzie m jest liczbą instrukcji w . Potrzebne w danej
chwili zawartości rejestrów odnajdujemy przeglądając 2. taśmę od lewej do prawej.
Wymagane są najwyżej dwa przejścia przez tę taśmę (w przypadku adresowania
pośredniego). 3. taśma zawiera bieżącą wartość �. 4. taśmę wykorzystujemy do
przechowywania adresu poszukiwanego rejestru. Za każdym razem, gdy czytamy parę
b(i) : b(ri), zawrtość 4. taśmy jest porównywana z b(i). Jeżeli są identyczne, to b(ri)
jest przenoszone na inne taśmy celem dlaszego przetworzenia. Wszystkie operacje
wykonujemy na pozostałych trzech taśmach. W przypadku operacji arytmetycznych
dwie taśmy zawierają argumenty, a wynik wyliczany jest na trzeciej taśmie. Po
obliczeniu aktualizujemy drugą taśmę. Na koniec symulacji instrukcji kolejny stan
rozpoczyna wykonanie następnej instrukcji progamu . Po dojściu do HALT, zawartość
rejestru 0 jest przenoszona z taśmy 2. na 7.
Musimy pokazać, że symulacja instrukcji programu  zabiera M czas O(f (n)2), gdzie n
jest długością danych. Zdekodowanie bieżącej instrukcji  i stałych w niej
występujących można wykonać w stałym czasie. Pobranie z 2. taśmy wartości rejestrów
zabiera M O(f (n2)) czasu (taśma 2. zawiera O(f (n)) par, każda długości O(f (n))), jak
wynika z lematu; samo przeszukanie może być dokonane w czasie liniowym). Obliczenie
wyniku składa się z prostych operacji arytmetycznych na liczbach całkowitych długości
O(f (n)), z których każda może być wykonana w czasie O(f (n)).
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 42 / 50
Maszyny niedeterministyczne
Maszyny niedeterministyczne
Wprowadzimy teraz nierealistyczny model obliczeń, który może być
symulowany przez wprowadzone wcześniej modele przy wykładniczym
wzroście czasu.
Niedeterministyczna maszyna Turinga jest czwórką N = (K, Ł, ", s),
gdzie K, Ł i s są takie, jak w zwykłej maszynie Turinga, natomiast "ma
możliwość wyboru między kilkoma akcjami, nie jest funkcją, lecz relacją:
" �" (K � Ł) � [(K *" {h,  tak ,  nie }) � Ł � {�!, , -}]  dla każdej
kombinacji stanu i symbolu może istnieć więcej niż jeden kolejny krok lub
nie istnieje żaden.
Konfigurację maszyn niedeterministycznych określamy tak samo, ale
przechodzenie nie jest funkcją, lecz relacją: Niedeterministyczna maszyna
Turinga N przechodzi w jednym kroku z (q, w, u)
N
do (q , w , u )  (q, w, u) (q , w , u )  jeżeli w " jest reguła, która
pozwala na takie przejście.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 43 / 50
Maszyny niedeterministyczne
Formalnie:
N
(q, w, u) (q , w , u ) ,
jeżeli istnieje ((q, �), (q , �, D)) " ", że albo
D = i w jest w z � zastąpionym przez � i dołączonym pierwszym
symbolem u, a u jest u bez pierwszego symbolu;
D =�! i w jest w bez �, a u jest u poprzedzonym przez �;
D = - i w jest w z � zastąpionym przez � i u jest u.
k "
N N
Relacje i definiujemy jak poprzednio.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 44 / 50
Maszyny niedeterministyczne
Niech L będzie językiem, a N niedeterministyczną maszyną Turinga. N
rozstrzyga L, jeżeli dla każdego x " Ł" jest prawdą, że x " L wtedy i tylko
"
N
wtedy, gdy (s, , x) ( tak , w, u) dla pewnych słów w i u
Niedeterministyczna maszyna Turinga N rozstrzyga język L w czasie f (n),
gdzie f jest funkcją z liczb naturalnych w liczby naturalne, jeżeli N
rozstrzyga L i ponadto dla dowolnego x " Ł", jeżeli
k
N
(s, , x) ( tak , w, u), to k d" f (|x|).
Zbiór języków rozstrzyganych przez niedeterministyczne maszyny Turinga
tworzy klasę złożoności NTIME(f (n)). Najważniejszą klasą złożoności
niedeterministycznej jest NP, suma wszystkich klas NTIME(nk).
Możemy natychmiast zauważyć, że P ą" NP, gdyż maszyny
deterministyczne są maszynami niedeterministycznymi, dla których " jest
funkcją.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 45 / 50
Maszyny niedeterministyczne
Przykład
Nie wiadomo, czy tsp (d) jest w P, łatwo jednak można zauważyć, że tsp (d)
jest w NP.
Istotnie, tsp (d) może być rozstrzygnięty przez niedetermininstyczną maszynę
Turinga w czasie O(n2). Maszyna ta dla słowa wejściowego zawierającego
reprezentację przykładu tsp zapisuje dowolny ciąg symboli niedłuższy niż słowo
wejściowe, po czym wraca na początek zapisanego słowa i sprawdza, czy
reprezentuje ono permutacją wszystkich miast. Jeżeli tak, to sprawdza jeszcze,
czy permutacja ta jest drogą o koszcie mniejszym niż B. Oba zadania mogą być
wykonane w czasie O(n2) przy użyciu 2. taśmy. Jeżeli wygenerowane słowo jest
rzeczywiście kodem drogi tańszej niż B, to jest akceptowane, w przeciwnym
wypadku  odrzucane.
Maszyna rzeczywiście rozstrzyga tsp (d), gdyż akceptuje słowo wejściowe wtedy
i tylko wtedy, gdy jest pozytywnym przykładem tsp (d)  jeżeli na wejściu
podany jest przykład pozytywny, to istnieje droga przechodząca przez wszystkie
miasta o koszcie niższym niż B, a więc istnieje obliczenie maszyny, które tę
permutację  odgadnie i sprawdzi, że ma niższy niż B koszt i zakończy się
akceptacją. Gdy takiej drogi nie ma, to maszyna nie może jej  odgadnąć i każde
słowo odrzuci.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 46 / 50
Maszyny niedeterministyczne
Twierdzenie
Jeżeli istnieje niedeterministyczna maszyna Turinga N rozstrzygająca język
L w czasie f (n), to istnieje deterministyczna maszyna Turinga o trzech
taśmach M , rozstrzygająca L w czasie O(cf (n)), gdzie c > 1 jest stałą
zależną od N .
Wynik ten można wyrazić przy pomocy klas złożoności:

NTIME(f (n)) ą" TIME(cf (n)) .
c>1
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 47 / 50
Maszyny niedeterministyczne
Dowód.
Niech N = (K, Ł, ", s). Dla każdego (q, �) " K � Ł rozważmy zbiór wyborów
Cq,� = {(q , � , D}: ((q, �), (q , � , D)) " "}. Cq,� jest zbiorem skończonym,
d = maxq,� |Cq,�|, d > 1.
Obliczenie N jest ciągiem t wyborów niedeterministycznych (c1, c2, . . . , ct), gdzie
cj " {0, 1, . . . , d - 1}. M rozważa wszystkie takie ciągi w kolejności rosnących długości
i symuluje N na każdym z nich. Rozważany ciąg (c1, c2, . . . , ct) M przechowuje na
drugiej taśmie. M symuluje działanie N , tak jak działałaby ona, gdyby dokonywała
wyboru ci w i-tym kroku. M symuluje w ten sposób t początkowych kroków N . Jeżeli
doprowadza to N do  tak , to M zatrzymuje się w  tak , w przeciwnym razie M bada
kolejny ciąg wyborów.
M wykrywa, że N odrzuca słowo wejściowe jeżeli sprawdzając działanie N na wszystkich
ciągach długości t nie odkryje żadnego obliczenia, które może być kontynuowane (tzn.
wszystkie kończą się w h lub  nie ).
Czas potrzebny M na symulację jest ograniczony przez liczbę ciągów wyboru
f (n)
dt = O(df (n)+1) razy czas konieczny do wygenerowania i rozważenia każdego
t=1
wyboru O(2f (n)).
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 48 / 50
Maszyny niedeterministyczne
Pamięć używaną przez maszyny niedeterministyczne definiujemy
rozszerzając definicję niedeterministycznej maszyny Turinga do
niedeterministycznej maszyny Turinga z wyróżnioną taśmą wejściową
i wyjściową.
Mówimy, że niedeterministyczna maszyna Turinga N = (K, Ł, ", s) z k
taśmami, w tym wyróżnioną taśmą wejściową i wyjściową, rozstrzyga język
L w pamięci f (n), jeżeli N rozstrzyga L i dodatkowo, jeżeli dla dowolnego
"
N
x " (Ł \ { })" zachodzi (s, , x, . . . , , ) (q, w1, u2, . . . , wk, uk), to
k-1
|wjuj| d" f (|x|).
j=2
Przykład
Algorytm deterministyczny dla reachibility wymagał pamięci liniowej. Na
maszynie niedeterministycznej wystarczy O(log n) pamięci.
Oprócz wejściowego używamy dwóch taśm: na 1. zapisujemy binarnie wierzchołek
i (początkowo 1), na 2. odgadniętą liczbę całkowitą j d" n (kolejny wierzchołek
ścieżki). Następnie sprawdzamy, czy bit (i, j) macierzy sąsiedztwa jest 1. Jeżeli
nie, maszynę zatrzymujemy i słowo odrzucamy. Jeżeli tak, to sprawdzamy, czy
j = n. Jeżeli tak, to kończymy i akceptujemy, jeżeli nie, to kopiujemy j na 1.
taśmę i całość powtarzamy.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 49 / 50
Maszyny niedeterministyczne
Niedeterministyczna maszyna Turinga nie jest rzeczywistym modelem
obliczeń. Niedeterminizm jest kluczowym pojęciem w teorii złożoności,
ponieważ skłania się ku zastosowaniom obliczeń, zwłaszcza w logice,
optymalizacji kombinatorycznej i sztucznej inteligencji. Logika zajmuje się
w dużej mierze dowodami  podstawowym pojęciem niedeterminizmu. Dla
zdania logicznego można wypróbować wszystkich możliwych dowodów
i uczynić je twierdzeniem, jeżeli jeden z dowodów będzie poprawny.
Kordian A. Smoliński (UA
) Złożoność obliczeniowa algorytmów 2007/2008 50 / 50