Złożoność obliczeniowa/Wykład 2: Inne modele dla złożoności

Wprowadzenie

W poprzednim rozdziale przedstawiliśmy bardzo prosty, ale zarazem potężny model obliczeń - maszynę Turinga. Przekonaliśmy się, że można na niej zaimplementować proste operacje takie jak dodawanie; nietrudno uwierzyć w to, że za jej pomocą można rozwiązywać również dużo bardziej skomplikowane problemy programistyczne.

Maszyna Turinga ma jednak zasadniczą wadę - programowanie na niej jest bardzo mało wygodne. W tym module poznamy dwa modele obliczeń dużo bardziej przypominające wygodne współczesne mikrokomputery takie jak ZX Spectrum.

Maszyna RAM

Schemat maszyny RAM.

Maszyna RAM (ang. Random Access Machine - maszyna o dostępie swobodnym) jest modelem obliczeń bardziej złożonym od maszyny Turinga. Składa się ona z programu - skończonego ciągu rozkazów definiujących jej działanie - oraz z potencjalnie nieograniczonego zbioru rejestrów, z których każdy może przechowywać dowolną liczbę naturalną. Rejestry indeksujemy liczbami naturalnymi, a więc ich wartości będziemy zapisywać jako $R_{0},R_{1},R_{2},\ldots$. Rejestr o indeksie 0 zwyczajowo nazywany jest akumulatorem i ma pewne specjalne (opisane poniżej) własności. Zbiór rejestrów zazwyczaj kolektywnie nazywamy pamięcią operacyjną lub po prostu pamięcią.

Oprócz programu i pamięci operacyjnej maszyna RAM posiada również dwie taśmy: wejściową i wyjściową. Podobnie jak taśmy maszyny Turinga składają się one z komórek, mogących zawierać symbole pewnego skończonego alfabetu; w przypadku maszyny RAM na taśmach wejściowej i wyjściowej znajdują się liczby naturalne z zakresu $[0,k]$, gdzie $k$ to liczba ustalona z góry dla danej maszyny. Różnicą w stosunku do maszyny Turinga jest to, że po dokonaniu zapisu na komórce taśmy wyjściowej głowica przesuwana jest w ustalonym kierunku (dla ustalenia uwagi w prawo) i nie można już do tej komórki powrócić; taśma wyjściowa nie może zatem służyć jako miejsce wykonywania obliczeń. To na programiście spoczywa odpowiedzialność zapisania fragmentów wyjścia w bezpiecznym miejscu, jeżeli planuje w przyszłości z nich skorzystać.

Zestaw instrukcji

W przeciwieńswie do maszyny Turinga, gdzie wszystkie wykonywane operacje były tego samego typu, maszyna RAM posiada stosunkowo złożony zestaw instrukcji. Warto przy tym zauważyć, że zestaw podany poniżej jest jednym z wielu możliwych zestawów instrukcji, które można znaleźć w literaturze. Zestawy te są zasadniczo równoważne (tzn. program napisany dla jednego z nich można przetłumaczyć na równoważny program dla innego zestawu instrukcji), mogą jednak wystąpić pewne niuanse przy rozważaniu złożoności obliczeniowej.

Kod	Symbol	Argument	Operacja
1	LOAD	=n	$R_{0}:=n$
2	LOAD	n	$R_{0}:=R_{n}$
3	LOAD	$\uparrow$n	$R_{0}:=R_{R_{n}}$
4	STORE	n	$R_{n}:=R_{0}$
5	STORE	$\uparrow$n	$R_{R_{n}}:=R_{0}$
6	READ	n	$R_{n}:=I$
7	READ	$\uparrow$n	$R_{R_{n}}:=I$
8	WRITE	n	$O:=R_{n}$
9	WRITE	$\uparrow$n	$O:=R_{R_{n}}$
10	NEXT		przesunięcie głowicy taśmy wejściowej w prawo
11	PREV		przesunięcie głowicy taśmy wejściowej w lewo
12	ADD	=n	$R_{0}:=R_{0}+n$
13	ADD	n	$R_{0}:=R_{0}+R_{n}$
14	ADD	$\uparrow$n	$R_{0}:=R_{0}+R_{R_{n}}$
15	SUB	=n	$R_{0}:=\max(R_{0}-n,0)$
16	SUB	n	$R_{0}:=\max(R_{0}-R_{n},0)$
17	SUB	$\uparrow$n	$R_{0}:=\max(R_{0}-R_{R_{n}},0)$
18	MUL	=n	$R_{0}:=R_{0}\cdot n$
19	MUL	n	$R_{0}:=R_{0}\cdot R_{n}$
20	MUL	$\uparrow$n	$R_{0}:=R_{0}\cdot R_{R_{n}}$
21	DIV	=n	$R_{0}:=R_{0}/n$
22	DIV	n	$R_{0}:=R_{0}/R_{n}$
23	DIV	$\uparrow$n	$R_{0}:=R_{0}/R_{R_{n}}$
24	JUMP	n	skok do instrukcji o numerze n
25	JZERO	n	skok do instrukcji o numerze n gdy $R_{0}=0$
26	JNZERO	n	skok do instrukcji o numerze n gdy $R_{0}\not =0$
27	HALT		zakończenie działania maszyny

W powyższej tabeli symbol I oznacza zawartość komórki taśmy wejściowej, znajdującej się pod głowicą. Analogicznie O to zawartość odpowiedniej komórki na taśmie wyjściowej.

Działanie maszyny RAM

W chwili początkowej konfiguracja maszyny wygląda następująco:

• wszystkie rejestry mają wartość 0,

• na taśmie wejściowej umieszczone jest słowo wejściowe; głowica taśmy wejściowej ustawiona jest na pierwszej (skrajnie lewej) komórce słowa wejściowego,

• licznik rozkazów wskazuje na pierwszą instrukcję programu.

W kolejnych krokach maszyna wykonuje instrukcje wskazywane przez licznik rozkazów. W przypadku instrukcji 1-23 po wykonaniu operacji na rejestrach lub taśmach licznik rozkazów zwiększany jest o jeden. W przypadku instrukcji skoku licznik rozkazów modyfikowany jest zgodnie z wartością argumentu (lub zwiększany o jeden, gdy skok jest warunkowy i warunek nie jest spełniony). Wykonanie instrukcji HALT kończy działanie programu. Dodatkowo instrukcja WRITE przesuwa głowicę taśmy wyściowej o jedną komórkę w prawo, a instrukcje NEXT i PREV przesuwają odpowiednio głowicę taśmy wejściowej.

Uwaga 2.1

Można się w tym momencie zastanawiać, co się stanie, gdy maszyna wykona ostatnią instrukcję programu i nie będzie to instrukcja HALT ani instrukcja skoku; albo też co się stanie, gdy jedna z instrukcji reprezentuje skok za ostatni rozkaz programu. Dla porządku przyjmiemy, że program zachowa się tak, jakby wykonał instrukcję HALT. Można też jednak przyjąć, że program dopuszczający taką sytuację jest niepoprawnie napisany i należy go poprawić - co nie jest zadaniem trudnym.

Wynikiem działania programu dla zadanego słowa wejściowego nazywamy ciąg liczb wypisanych na taśmę wyjściową od rozpoczęcia działania programu aż do wykonania instrukcji HALT.

Przykład 2.2

Poniższy program liczy największy wspólny dzielnik dwóch liczb naturalnych podanych na wejściu:

1. READ 1
2. NEXT
3. READ 2
4. LOAD 2
5. JZERO 19
6. SUB 1
7. JNZERO 12
8. LOAD 1
9. SUB 2
10. STORE 1
11. JUMP 4
12. LOAD 2
13. STORE 3
14. LOAD 1
15. STORE 2
16. LOAD 3
17. STORE 1
18. JUMP 4
19. WRITE 1
20. HALT

Jest on generalnie równoważny poniższemu programowi w języku Pascal:

function gcd(a:integer; b:integer):integer;
var
    c:integer;
begin
  while b <> 0 do         {linie 4-5}
  begin
    if a >= b then        {linie 6-7}
      a := a - b          {linie 8-10}
    else
    begin
      c := b;             {linie 12-13}
      b := a;             {linie 14-15}
      a := c;             {linie 16-17}
    end;
  end;
  gcd := a;
end;

Rozpoznawanie języków

Większość problemów omawianych w ramach tego kursu jest natury decyzyjnej - to znaczy dla zadanego słowa wejściowego program ma udzielić odpowiedzi tak lub nie. Warto zatem umówić się, w jaki sposób maszyna ma nam zakomunikować swoją odpowiedź.

Definicja 2.3

Mówimy, że maszyna RAM akceptuje słowo wejściowe w wtedy i tylko wtedy, gdy po uruchomieniu jej ze słowem w umieszczonym na taśmie wejściowej wypisuje ona na taśmę wyjściową dokładnie jedną liczbę - 1 - i zatrzymuje się po skończonej ilości kroków. Językiem akceptowanym przez maszynę RAM nazywamy zbiór wszystkich skończonych słów akceptowanych przez tę maszynę.

Ćwiczenie 2.4

Uzasadnij, dlaczego żądamy, żeby rejestry maszyny RAM mogły przechowywać dowolnie duże liczby naturalne.

Wskazówka

Zastanów się, z jakiej funkcjonalności maszyny RAM korzystamy, jeśli do wykonania obliczenia potrzebujemy ilości pamięci rosnącej wraz ze wzrostem wielkości wejścia.

Rozwiązanie

Kluczem do odpowiedzi na postawione pytanie jest zastosowanie w maszynie RAM adresowania pośredniego - trybu adresowania, oznaczanego powyżej za pomocą symbolu $\uparrow$. Warto zauważyć, że jeśli nasz program nie korzysta z adresowania pośredniego, to w trakcie swojego działania używa ustaloną z góry, skończoną liczbę rejestrów; dla przykładu powyższy program, liczący największy wspólny dzielnik, korzysta tylko z rejestrów o numerach 0-3. Jeżeli jednak do wykonania programu potrzebujemy potencjalnie nieograniczonej ilości pamięci, będziemy zmuszeni do skorzystania z adresowania pośredniego.

Adresowanie pośrednie jest kluczową cechą maszyny RAM; poniższe ćwiczenie ma na celu zaznajomienie Cię z jego działaniem.

Ćwiczenie 2.5

Zasymuluj program maszyny Turinga z przykładu 2 w module 1 (realizujący dodawanie dwóch liczb unarnych) na maszynie RAM. Oblicz, ile najwięcej kroków wykonuje skonstruowana przez Ciebie maszyna RAM podczas jednego kroku symulowanej maszyny Turinga. Jeśli liczba takich kroków nie jest ograniczona, popraw maszynę w ten sposób, aby ta liczba była ograniczona.

Wskazówka

Zauważ, że w trakcie działania wspomnianej maszyny Turinga głowica nigdy nie znajduje się na lewo od swojej pozycji początkowej.

Rozwiązanie

Załóżmy, że znak pusty (#) reprezentowany jest na wejściu maszyny RAM jako liczba 2. Program może wyglądać wtedy następująco:

# przepisanie wejścia do rejestrów
1. LOAD =2
2. STORE 1
3. READ ↑1
4. NEXT
5. LOAD =2
6. SUB ↑1
7. JZERO 12
8. LOAD =1
9. ADD 1
10. STORE 1
11. JUMP 3
# stan A
12. LOAD =2
13. STORE 1
14. LOAD =2
15. SUB ↑1
16. JZERO 22
17. LOAD =1
18. STORE ↑1
19. ADD 1
20. STORE 1
21. JUMP 14
22. LOAD 1
23. SUB =1
24. STORE 1
# stan B
25. LOAD =2
26. STORE ↑1
27. LOAD 1
28. SUB =1
29. STORE 1
# stan C
30. LOAD =2
31. STORE ↑1
32. LOAD =1
33. ADD 1
# wypisanie wyjścia
34. LOAD =2
35. STORE 1
36. LOAD =2
37. SUB ↑1
38. JZERO 44
39. WRITE ↑1
40. LOAD =1
41. ADD 1
42. STORE 1
43. JUMP 36
44. HALT

W powyższym programie w komórce numer 1 przechowywana jest pozycja symulowanej głowicy. Górnym ograniczeniem na ilość kroków maszyny RAM przy symulacji jednego kroku maszyny Turinga jest w powyższym przypadku liczba 13 (w stanie A) -- widzimy zatem, że liczba kroków maszyny RAM (nie licząc przepisywania słów wejściowych i wyjściowych) jest liniowo zależna od liczby kroków maszyny Turinga.

Powyższe ćwiczenie ilustruje ważną własność - każdy program dla jednotaśmowej, jednostronnie ograniczonej (czyli posiadającej nieskończoną taśmę tylko w jednym kierunku) maszyny Turinga można w prosty sposób przekształcić na równoważny program maszyny RAM. Łatwo się przekonać, że maszyna Turinga z obustronnie nieograniczoną taśmą nie jest potężniejsza od maszyny z taśmą jednostronnie ograniczoną; aby przekształcić program napisany dla pierwszej z nich wystarczy umówić się, że komórki o nieparzystych numerach będą reprezentowały komórki oryginalnej maszyny o ujemnych numerach, a komórki o parzystych numerach będą reprezentowały komórki oryginalnej maszyny o numerach dodatnich; dodatkowo należy w dość prosty sposób zmodyfikować program.

Złożoność obliczeniowa w modelu RAM

Zastanówmy się teraz, w jaki sposób można określić czas i pamięć zużyte w trakcie działania maszyny RAM. Pierwszy - zapewne wyglądający na najbardziej naturalny - sposób definiowania tych wielkości to tak zwane kryterium jednostajne. Jego założenia są następujące:

• uznajemy, że każdy rozkaz maszyny jest wykonywany w pewnym z góry ustalonym, stałym czasie,

• uznajemy, że miarą pamięci "zużytej" przez program w trakcie działania jest ilość rejestrów, do których program się odwoływał (w postaci odczytu lub zapisu).

Takie podejście po chwili zastanowienia nie wydaje się jednak właściwe; co gorsza - założenie o wykonywaniu operacji arytmetycznych na dowolnie dużych liczbach w stałym czasie nie jest obecnie możliwe do zrealizowania, i nie wygląda na to, aby mogło zostać zrealizowane również w przyszłości.

Będziemy zatem stosować inne miary dla czasu i pamięci, zwane kryterium logarytmicznym. Jego założenia są następujące:

• czas wykonania operacji na liczbie $n$ jest proporcjonalny do $\lfloor \log n\rfloor +1$. Czas wykonania operacji na dwóch liczbach $m$ i $n$ jest proporcjonalny do $\lfloor \log(m+n)\rfloor +1$ (oczywiście trzeba pamiętać, że logarytm liczby $0$ jest niezdefiniowany; koszt wykonania operacji w tym przypadku równy jest $0$),

• jeżeli operacja używa adresowania pośredniego, to czas dostępu do $k$-tej komórki jest proporcjonalny do $\lfloor \log k\rfloor +1$,

• do czasu wykonania każdej operacji doliczana jest pewna stała wielkość, mogąca reprezentować koszt pobrania i rozpoznania instrukcji. Chodzi tutaj głównie o to, by programy wykonujące same instrukcje skoku lub trywialne (czyli w tym przypadku operujące na samych zerach) operacje arytmetyczne miały niezerowy czas działania,

• jako miarę pamięci używanej przez program w danym momencie uznajemy

sumę logarytmów wartości wszystkich rejestrów, do których odwoływał się program w trakcie swojego dotychczasowego działania.

Tak zdefiniowane miary ilości zasobów dużo lepiej odpowiadają rzeczywistości współczesnych komputerów - do zapisania w pamięci liczby $n$ potrzebujemy $\lfloor \log n\rfloor +1$ cyfr w systemie binarnym, natomiast dodanie dwóch liczb $m$ i $n$ zajmuje czas $O(\log(m+n))$. Niedoszacowany może się wydawać czas mnożenia i dzielenia (jest taki sam jak dodawania), jednak, jak się okaże, dla naszych celów taka definicja zupełnie wystarczy.

Porównanie czasu działania maszyny Turinga i maszyny RAM

Uwaga 2.6

Umówmy się, że czas działania określamy tylko dla maszyn z własnością stopu - zarówno w przypadku maszyn Turinga i maszyn RAM.

W jednym z poprzednich ćwiczeń symulowaliśmy działanie maszyny Turinga na maszynie RAM; stwierdziliśmy, że liczba kroków wykonywanych przez maszynę RAM jest proporcjonalna do liczby kroków wykonanych przez symulowaną maszynę Turinga. Jeżeli zatem $T(n)$ określa największą ilość kroków wykonywaną przez daną maszynę Turinga przy słowie wejściowym o długości $n$, a $T'(n)$ jest analogicznie zdefiniowaną maksymalną ilością kroków dla maszyny RAM, to zachodzi następująca własność:

$T'(n)=O(T(n))$.

Uwaga 2.7

W rzeczywistości w tym momencie powinniśmy zapisać:

$T'(n)=O(T(n)+n)$.

Skąd się wzięło $n$? Otóż maszyna Turinga może dać odpowiedź jeszcze przed przeczytaniem całego słowa wejściowego. Maszyna RAM, skonstruowana w zaprezentowany we wspomnianym ćwiczeniu sposób, symulująca działanie maszyny Turinga, przed rozpoczęciem symulacji przepisze całe słowo wejściowe do rejestrów, po czym dopiero rozpocznie właściwe działanie. Można jednak łatwo wyobrazić sobie schemat, w którym maszyna RAM sprowadza znaki z wejścia niejako "na żądanie", zapamiętując jednocześnie liczbę sprowadzonych wcześniej znaków. Taki schemat postępowania sprawia, że własność:

$T'(n)=O(T(N))$

naprawdę zachodzi.

Zauważmy, że powyższa definicja funkcji czasu $T'(n)$ dokładnie odpowiada definicji złożoności czasowej przy zastosowaniu kryterium jednostajnego. Warto się zastanowić, jak będzie wyglądała złożoność obliczeniowa w przypadku zastosowania kryterium logarytmicznego.

Ćwiczenie 2.8

Oszacuj czas działania maszyny RAM, symulującej działanie maszyny Turinga, przy zastosowaniu kryterium logarytmicznego.

Wskazówka

Wskaż instrukcje maszyny RAM, które nie są wykonywane w stałym czasie i oszacuj ich czas działania.

Rozwiązanie

Należy zauważyć, że jedynym rejestrem, którego zawartości nie można a priori oszacować przez stałą, jest rejestr przechowujący pozycję symulowanej głowicy. Pozycję tę można jednak w prosty sposób oszacować od góry - nie będzie ona nigdy większa niż $T(n)$. Operacje o zmiennym czasie działania - czyli zwiększanie i zmniejszanie wskaźnika pozycji głowicy oraz dostęp za pomocą adresowania pośredniego do komórki pod głowicą - odbywają się w czasie $O(logT(n))$. Jeżeli zatem jako $T''(n)$ oznaczymy pesymistyczny czas działania maszyny RAM w zależności od wielkości wejścia, to możemy zapisać następujący fakt: $T''(n)=O(T(n)logT(n))$,

a rozluźniając nieco oszacowanie:

$T''(n)=O(T(n)^{2})$.

Symulowanie maszyny RAM na wielotaśmowej maszynie Turinga

Wyniki z poprzedniego paragrafu nie są specjalnie zaskakujące; gołym okiem widać, że maszyna RAM jest narzędziem co najmniej równie potężnym jak maszyna Turinga. W tym paragrafie zajmiemy się zagadnieniem odwrotnym - pokażemy, że maszynę RAM da się symulować na maszynie Turinga i oszacujemy wydajność takiej symulacji.

Aby tego jednak dokonać, uprościmy sobie najpierw definicję maszyny RAM. Będziemy zatem tylko rozpatrywać maszyny RAM spełniające następujące warunki:

• wejście i wyjście stanowią słowa nad alfabetem $\{0,1\}$,

• maszyna nie używa instrukcji MUL ani DIV,

• jedynymi operacjami, dopuszczającymi adresowanie pośrednie, są instrukcje LOAD i STORE.

Maszynę RAM będziemy symulować na wielotaśmowej maszynie Turinga, posiadającej:

• taśmę wejściową nad alfabetem $\{0,1\}$,

• taśmę wyjściową nad alfabetem $\{0,1\}$,

• cztery taśmy robocze nad alfabetem $\{0,1,\$,*,\%\}$.

Maszyna Turinga będzie symulowała po kolei rozkazy maszyny RAM, przy czym zakładamy, że na początku symulacji każdego rozkazu głowice taśm roboczych znajdują się w takim położeniu, jak na początku działania programu. Taśma robocza nr 1 będzie służyła do reprezentacji aktualnej zawartości rejestrów maszyny RAM. Taśma robocza nr 2 będzie służyła do przechowywania jednego adresu komórki. Taśmy robocze 3 i 4 będą służyły do wykonywania operacji arytmetycznych. Najciekawiej wygląda taśma nr 1; sposób reprezentacji pamięci RAM jest przedstawiony na poniższym schemacie:

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \verb''\$011*01*11*101**1011\$} .

Na taśmie znajdują się pary liczb, zapisane w postaci binarnej, zaczynając od najmniej znaczącej cyfry. Powyższy zapis mówi, że:

• rejestr 6 ma wartość 2,

• rejestr 3 ma wartość 5,

• rejestr 0 ma wartość 13 (zakładamy, że reprezentacja binarna liczby 0 ma 0 cyfr).

Prześledźmy teraz działanie maszyny dla operacji ADD n (przypominamy, że nie jest tutaj stosowane adresowanie pośrednie, zatem $n$ jest stałą określoną w czasie pisania programu). Maszyna Turinga zachowa się w następujący sposób:

• na taśmie numer 2 zapisze ciąg symboli $\$\langle reprezentacja\_binarna\_liczby\_n\rangle \$$, po czym przesunie głowicę tej taśmy do położenia początkowego,

• przesuwając się w prawo na taśmie nr 1, maszyna będzie szukać reprezentacji komórki o numerze $n$; w tym celu będzie porównywać numery komórek, zapisane na taśmie nr 1, z adresem zapisanym na taśmie nr 2. Jeśli adresy się nie będą zgadzały maszyna wycofa głowicę taśmy nr 2 do położenia początkowego, zignoruje zawartość komórki na taśmie nr 1 i przejdzie do następnej pary adres-zawartość,

• jeżeli maszyna znajdzie odpowiedni adres, to przepisze zawartość komórki na taśmę nr 3. W przeciwnym wypadku - gdy dojdzie do symbolu - zapisze na taśmie nr 3 reprezentację liczby 0,

• podobna procedura zostanie zastosowana do przekopiowania na taśmę nr 4 zawartości akumulatora (rejestru o numerze 0),

• maszyna doda liczbę zawartą na taśmie nr 3 do liczby z taśmy nr 4 za pomocą algorytmu pisemnego dodawania liczb binarnych,

• maszyna zapisze wynik dodawania na taśmie nr 1.

Ostatni krok może nastręczyć pewnych problemów: nie wiemy, co powinniśmy zrobić, jeśli wynik dodawania zajmuje więcej bitów niż oryginalna liczba zawarta w akumulatorze. Rozwiązanie w tym przypadku jest bardzo brutalne: nasza maszyna po prostu zapisze wynik na samym końcu taśmy nr 1; jeżeli po drodze na koniec taśmy napotka parę adres-wartość, odpowiadającą akumulatorowi, to zarówno adres jak i wartość oraz występujący między nimi separator Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \'\*\'} zamaże, wpisując w ich miejsca symbole $\%$. Na poniższym schemacie przedstawiony jest stan taśmy nr 1 po wykonaniu operacji ADD 3 (dodanie do akumulatora zawartości komórki 3):

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \verb''\$011*01*11*101**\%\%\%\%**01001\$} .

Operacja $LOAD\uparrow n$ nie jest dużo bardziej skomplikowana; trzeba znaleźć zawartość komórki $n$, następnie znaleźć zawartość komórki $R_{n}$, a na końcu zapisać wynik w akumulatorze (w razie potrzeby zamazując jego poprzednią zawartość).

Oszacujemy teraz czas potrzebny do zasymulowania maszyny RAM. Wykonanie operacji arytmetycznych (pomijając czas dostępu do pamięci) zajmuje czas $O(log(m+n))$, gdzie $m$ i $n$ to argumenty operacji. Operacja kopiowania zawartości jednego rejestru do drugiego zajmuje czas $O(logn)$, gdzie $n$ to kopiowana wartość. Stwierdzamy zatem, że samo wykonanie operacji na maszynie Turinga jest "wolniejsze" od wykonania tych operacji na maszynie RAM o stały czynnik. Innymi słowy, jeśli $T(n)$ to czas wykonania programu dla danych o wielkości $n$ na maszynie RAM, a $T'(n)$ to czas wykonania (pomijając dostępy do pamięci) tych samych operacji na maszynie Turinga, to zachodzi następująca własność:

$T'_{1}(n)=O(T(n))$

Pozostaje zatem kwestia oszacowania, ile zajmuje wyszukiwanie (i ewentualne zamazywanie) komórek na taśmie nr 1. Łatwo jednak zauważyć, że w każdym momencie symulacji ilość symboli na taśmie 1 jest co najwyżej proporcjonalna do czasu działania symulowanej maszyny RAM. Zatem czas łącznie spędzony przez maszynę Turinga na dostępy do pamięci można oszacować w następujący sposób:

$T'_{2}(n)=O(T(n)\cdot T(n))=O(T(n)^{2})$.

Zatem łączny czas działania maszyny Turinga - a więc czas dostepu do pamięci plus czas właściwych operacji - spełnia własność:

$T'(n)=O(T(n)^{2})$.

Ćwiczenie 2.9

Oszacuj zależność między złożonością czasową programu dla maszyny RAM a złożonością czasową programu maszyny Turinga, symulującego działanie maszyny RAM, przy założeniu, że program maszyny RAM może używać wszystkich rozkazów.

Wskazówka

Przekształć wywołania "zabronionych" rozkazów maszyny RAM na sekwencje rozkazów "dozwolonych" i oszacuj czas wykonania tych sekwencji.

Rozwiązanie

To oczywiste, że adresowanie pośrednie dla operacji innych niż LOAD i STORE jest łatwe do zasymulowania: wystarczy zastąpić te operacje poprzez sekwencje wykorzystujące akumulator i być może pewne z góry ustalone tymczasowe rejestry, w przypadku gdy trzeba będzie odtworzyć zawartość akumulatora.

Pozostają więc operacje MUL i DIV. Zaczniemy od MUL =2 i DIV =2. Widać, że operacja MUL =2 jest prosta do zaimplementowania za pomocą dodawania. Operację DIV =2 można zaimplementować w sposób opisany za pomocą poniższego pseudokodu:

function div2(n:integer):integer;
var
   a, b, c, res:integer;
begin
 res := 0;

 while n >= 2 do
 begin
  a := 4;
  b := 2;
  c := 1;

  while n >= a do
  begin
   a := 2 * a;
   b := 2 * b;
   c := 2 * c;
  end;

  n := n - b;
  res := res + c;
 end;

 div2 := res;
end;

W skrócie działanie tej procedury można opisać następująco: procedura znajduje największą potęgę dwójki nie większą od argumentu (czyli najbardziej znaczący bit) i dodaje do wyniku tę liczbę podzieloną przez 2 (czyli bit przesunięty o jedną pozycję w prawo). Każda pętla iteruje się co najwyżej $O(logn)$ razy, a operacje wewnątrz niej zajmują czas $O(logn)$ - zatem powyższa procedura działa w czasie $O(log^{3}n)$. Warto też zauważyć, że używana jest tutaj stała liczba zmiennych tymczasowych, o rozmiarze porównywalnym do rozmiaru liczby $n$.

Powyższa procedura pozwala na prostą implementację funkcji MOD = 2 - czyli funkcji zwracającej najmniej znaczący bit liczby. Z wykorzystaniem tej funkcji możemy zaimplementować mnożenie dwóch dowolnych liczb:

function multiply(n:integer; m:integer):integer;
begin
 res := 0;

 while n > 0 do
 begin
  if n mod 2 = 1 then
   res := res + m;

  n := n div 2;
  m := m mul 2;
 end;

 multiply := res;
end; 

Czas działania powyższej procedury można oszacować od góry jako $O(log^{4}(n+m))$.

Do zaimplementowania pozostało nam już zatem tylko dzielenie; można tą procedurę skonstruować w następujący sposób:

function divide(n:integer; m:integer):integer;
var
    lo, hi, med:integer;
begin
 lo := 0;
 hi := 1;

 while m * hi <= n do
  m := 2 * m;

 while (hi - lo) > 1 do
 begin
  med := (lo + hi) div 2;

  if med * hi <= n then
   lo := med
  else
   hi := med;
  end;

 divide := lo;
end;

Tutaj złożoność czasową można oszacować przez $O(log^{5}(n+m))$.

Widzimy zatem, że każdą "zabronioną" operację arytmetyczną można zasymulować w czasie $O(log^{5}(n+m))$. W związku z tym każdy program maszyny RAM działający w czasie $O(T(n))$ można przekształcić w równoważny program nie korzystający z "zabronionych" operacji i działający w czasie $O(T(n)^{5})$.

W powyższych procedurach zdecydowanie większa waga była przyłożona do prostoty rozwiązania niż do jego wydajności; również przedstawione powyżej odgórne oszacowanie jest bardzo zgrubne - jest ono prawdziwe w przypadku, gdy w programie często używane jest dzielenie dużych liczb.

Powyższe paragrafy pokazały zależność pomiędzy złożonościami czasowymi równoważnych programów dla maszyn RAM i Turinga. Taką zależność pomiędzy modelami obliczeń nazywamy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \textit{wielomianową równoważnością}} .

Definicja 2.10

Mówimy, że modele obliczeń ${\mathcal {A}}$ i ${\mathcal {B}}$ są wielomianowo równoważne (w sensie złożoności czasowej) wtedy i tylko wtedy, gdy dla dowolnego języka $L\subseteq \Sigma ^{\star }$ (gdzie $\Sigma$ jest skończonym alfabetem):

• istnienie programu dla maszyny modelu ${\mathcal {A}}$ o złożoności czasowej $f(n)$ implikuje istnienie programu dla maszyny modelu ${\mathcal {B}}$ o złożoności czasowej $O(w(f(n)))$, gdzie $w(x)$ jest wielomianem,

• zachodzi własność symetryczna.

Wielomianowa równoważność sprawia, że jeśli dla danego problemu na maszynie jednego typu istnieje algorytm o wielomianowej złożoności czasowej, to również na drugiej maszynie istnieje algorytm o wielomianowej złożoności czasowej.

Porównanie złożoności pamięciowej w modelach obliczeniowych

Do tej pory mało uwagi poświęcaliśmy złożoności pamięciowej w obu poznanych modelach obliczeniowych. Spróbujmy zatem analogicznie jak poprzednio oszacować pamięć zużytą przez równoważne programy dla maszyny RAM i maszyny Turinga. Ponownie w przypadku maszyny RAM będziemy używali kryterium logarytmicznego.

Łatwo zauważyć, że podczas symulacji maszyny Turinga na maszynie RAM jedynym rejestrem, którego zawartość nie będzie z góry ograniczona przez pewną stałą, jest rejestr zawierający pozycję głowicy. Jego zawartość będzie miała rozmiar co najwyżej logarytmicznie zależny od ilości komórek zużytych na maszynie Turinga. Koszt każdego pozostałego użytego rejestru -- służącego do symulacji komórki maszyny Turinga -- będzie ograniczony przez stałą zależną od alfabetu symulowanej maszyny. Sumaryczna ilość pamięci zużytej przez maszynę RAM będzie zatem liniowo zależna od ilości pamięci zużytej przez maszynę Turinga.

Przejdźmy teraz do symulacji maszyny RAM na maszynie Turinga. W podanej wcześniej procedurze symulacji zachowywaliśmy się dość niechlujnie -- jeżeli symulowana maszyna RAM zapisywała nową wartość do używanego wcześniej rejestru, maszyna Turinga po prostu zamazywała poprzednią wartość i zapisywała nową wartość na koniec taśmy. Można tą procedurę jednak łatwo zmodyfikować -- zamiast zamazywania poprzedniej wartości można przesunąć wszystkie kolejne zapisane na taśmie wartości rejestrów do zwolnionych komórek maszyny Turinga, po czym zapisać nową wartość rejestru na końcu taśmy. Modyfikacja ta sprawi, że ilość komórek używanych przez maszynę Turinga będzie liniowo zależna od ilości pamięci używanej przez symulowaną maszynę RAM; co ważne, czas działania maszyny Turinga nadal będzie wielomianowo zależny od czasu działania maszyny RAM.

Widzimy zatem, że w przypadku złożoności pamięciowej podobieństwo maszyny Turinga i maszyny RAM jest jeszcze silniejsze niż w przypadku złożoności czasowej. Dwie powyższe własności sprawiają, że w dalszej części tego wykładu będziemy używać tych dwóch modeli zamiennie -- dla naszych celów będą one równoważne.

Obwody logiczne

Rozważymy teraz model obliczeń w znaczący sposób różniący się od dwóch poprzednio opisanych -- obwody logiczne. Obwód logiczny można formalnie zdefiniować jako acykliczny graf skierowany o następujących własnościach:

• każdy wierzchołek jest wierzchołkiem wejściowym, wierzchołkiem wyjściowym, koniunkcją, alternatywą albo negacją,

• w zależności od typu wierzchołka spełnione są ograniczenia na jego stopnie wejściowe i wyjściowe:
  • wierzchołek wejściowy - stopień wejściowy 0,
  • wierzchołek wyjściowy - stopień wejściowy 1, stopień wyjściowy 0,
  • alternatywa i koniunkcja - stopień wejściowy 2,
  • negacja - stopień wejściowy 1.

Węzły wewnętrzne - koniunkcję, alternatywę i negację - zwyczajowo nazywa się bramkami. Ich semantyka zgodna jest z powszechnie przyjętym w logice zwyczajem. Załóżmy, że obwód logiczny ma $m$ wejść i $n$ wyjść, z pewnym ustalonym na nich porządkiem. Możemy wtedy patrzeć na układ logiczny jako na funkcję następującego typu:

$f:\{0,1\}^{m}\rightarrow \{0,1\}^{n}$.

Ćwiczenie 3.1

Skonstruuj układ logiczny, obliczający funkcję XOR.

Rozwiązanie

Jeden z możliwych układów przedstawiony jest na poniższym rysunku.

Implementacja funkcji XOR.

Stopień skomplikowania układu można mierzyć na dwa sposoby:

• poprzez ilość bramek w układzie logicznym,

• poprzez ilość bramek na najdłuższej ścieżce występującej w układzie (głębokość układu logicznego).

W dalszej części tego rozdziału będziemy się zajmować pierwszą z tych miar.

W odróżnieniu od dwóch poprzednich modeli, każdy układ logiczny ma z góry określoną wielkość wejścia i wyjścia, a co za tym idzie, skończoną liczbę możliwych zestawów danych wejściowych. Dla takiej rodziny układów będziemy określać miarę złożoności ilościowej.

Definicja 3.2 [Miara złożoności ilościowej]

Niech ${\mathcal {R}}$ będzie rodziną układów logicznych taką, że dla każdej liczby naturalnej $n$ rodzina zawiera dokładnie jeden układ o $n$ węzłach wejściowych. Miarą złożoności ilościowej nazwiemy wtedy funkcję $f:\mathbb {N} \rightarrow \mathbb {N}$, która każdej liczbie naturalnej $n$ przyporządkowuje liczbę bramek zawartych w jedynym układzie z ${\mathcal {R}}$, posiadającym $n$ wejść.

Pokażemy teraz, jaki jest związek między złożonością czasową obliczenia na maszynie Turinga (rozpoznającej pewien język $L$) a złożonością czasową rodziny układów logicznych rozpoznających ten sam język. W tym celu zasymulujemy działanie jednotaśmowej maszyny Turinga dla słów wejściowych o ustalonej długości.

Załóżmy zatem, że maszyna Turinga $M$ rozpoznaje język $L$, jej alfabet taśmowy zawiera $k$ elementów, a zbiór stanów zawiera $s$ elementów. Załóżmy dodatkowo, że maszyna w trakcie swojego działania nie musi w każdym ruchu przesuwać głowicy - może ją pozostawiać w miejscu; ponadto zażądajmy, by maszyna po ustaleniu wyniku działania wracała do położenia początkowego i przechodziła do stanu akceptującego (a dokładniej, żeby się w tym stanie "zapętlała"). Łatwo zauważyć, że każdą maszynę można "zmusić" do tego, aby spełniała te założenia, nie zwiększając jej czasu działania więcej niż dwukrotnie. Złożoność czasową tej maszyny oznaczmy jako $T(n)$.

Ustalmy teraz pewną długość słowa wejściowego - $n$; ponieważ znamy złożoność czasową maszyny $M$, możemy jeszcze przed rozpoczęciem działania stwierdzić, ile maksymalnie może jej zająć rozwiązywanie problemu decyzyjnego i ile najwięcej może zużyć miejsca podczas tego procesu. Skonstruujemy zatem następujący układ logiczny, z $\lceil \log k\rceil \cdot n$ wejściami, symulujący maszynę $M$ - jego schemat przedstawiony jest na poniższym rysunku:

Układ logiczny symulujący maszynę Turinga.

Na powyższym schemacie prostokąty reprezentują pewne podukłady logiczne. "Wyjścia" (czyli wartości węzłów na "dolnej" warstwie) prostokątów na $i$-tej warstwie reprezentują konfigurację maszyny po $i$ krokach. Wyjście $j$-tego prostokąta na $i$-tej warstwie składa się z $w=\lceil logk\rceil +\lceil log(s+1)\rceil$ węzłów (bitów). Pierwsza część wyjścia oznacza symbol, który znajduje się w $j$-tej komórce taśmy maszyny Turinga po $i$ krokach. Pozostała część mówi, czy w $i$-tym kroku głowica znajduje się nad $j$-tą komórką i jeśli tak, w jakim stanie znajduje się maszyna (robimy to dodając jeden "sztuczny" stan, mówiący, że w danym miejscu nie ma głowicy; stąd na zapisanie stanu potrzebne jest $\lceil log(s+1)\rceil$ bitów). Zastanówmy się teraz, jakie powinno być zachowanie typowego "prostokąta" (oznaczonego symbolem A). Wynik działania tego podukładu zależy tylko i wyłącznie od wyników działania trzech podukładów z poprzedzającej go warstwy; jego funkcja jest zdefiniowana przez zachowanie maszyny Turinga, to znaczy:

• jeśli żadna z trzech komórek poprzedniej warstwy nie zawierała głowicy, to należy przepisać symbol taśmy z prostokąta położonego bezpośrednio nad rozpatrywanym układem,

• jeśli prostokąt położony bezpośrednio nad rozpatrywanym układem posiadał symulowaną głowicę, to należy odpowiednio zmodyfikować otrzymany od niego symbol taśmowy i - w zależności od tego czy głowica się przesuwa, czy nie - zapisać stan symulowanej maszyny lub zapisać sztuczny stan "brak głowicy",

• analogiczne zasady (oczywiście odpowiednio zmodyfikowane) dla sytuacji, gdy głowica na warstwie o numerze $i-1$ znajdowała się w jednej z dwóch sąsiadujących z rozpatrywaną komórek.

Prostokąty A reprezentują więc pewne z góry określone funkcje typu $\{0,1\}^{3w}\rightarrow \{0,1\}^{w}$. Wiedząc, że układ operatorów $\{\wedge ,\vee ,\neg \}$ jest układem funkcjonalnie pełnym, można stwierdzić, że prostokąt A jest implementowany przez określoną z góry, stałą liczbę bramek (oznaczmy ją $c_{1}$; stała ta jest zależna tylko od funkcji przejścia - w szczególności nie jest w żaden sposób zależna od $n$). Rozumując analogicznie, możemy też stwierdzić, że prostokąty B, C, D i E reprezentują pewne funkcje logiczne i możemy je zaimplementować z użyciem co najwyżej $c_{2}$ bramek.

Pozostaje nam tylko ustalić, jak obliczamy wartość wyjścia układu logicznego; tutaj postępowanie jest proste z powodu wymagań, jakie nałożyliśmy na maszynę: maszyna $M$ akceptuje słowo wtedy i tylko wtedy, gdy po $T(n)$ krokach głowica znajduje się w pozycji początkowej i maszyna jest w ustalonym stanie akcpetującym. Oba te warunki można sprawdzić na podstawie wyjścia podukładu reprezentowanego przez środkowy prostokąt $T(n)$-tej warstwy.

Przedstawiliśmy zatem sposób, w jaki dla algorytmu o złożoności czasowej $T(n)$ można skonstruować rodzinę układów logicznych o:

$c_{1}(2T(n)-1)\cdot T(n)+c_{2}(4T(n)+1)=O(T(n)^{2})$

bramkach.

Wniosek 3.3

Jeżeli dla określonego problemu decyzyjnego istnieje algorytm dla maszyny Turinga o wielomianowej złożoności czasowej, to istnieje rodzina układów logicznych o wielomianowej złożoności ilościowej, rozwiązująca ten sam problem decyzyjny.

Kontrapozycja tego wniosku jest czasami używana do pokazywania, że dla danego problemu nie istnieje algorytm wielomianowy.