Języki, automaty i obliczenia/Wykład 13: Złożoność obliczeniowa.

From Studia Informatyczne

Sformułujemy definicje podstawowych klas złożoności w języku maszyn Turinga oraz metodę ich porównywania. Przeanalizujemy związki między rodziną języków określonych przez maszyny Turinga a rodziną języków typu (0) z hierarchii Chomsky'ego. Podamy dalsze własności języków kontekstowych i typu (0). Wprowadzimy pojęcie języka rekurencyjnie przeliczalnego oraz przedstawimy tezę Churcha. Następnie omówimy teoretyczne podstawy teorii rozstrzygalności oraz przeanalizujemy kilka problemów nierozstrzygalnych w teorii języków.


Spis treści

Klasy złożoności obliczeniowej

Jednym z podstawowych celów wprowadzania maszyn Turinga jest dążenie do formalnej definicji złożoności obliczeniowej. Na podstawie wcześniejszych uwag możemy utożsamiać akceptację słowa przez maszynę Turinga z jej zatrzymaniem się. Intuicyjnie, można takie zachowanie maszyny Turinga utożsamić z wykonaniem programu, który zwraca odpowiedź "Tak" na postawione przez nas pytanie.

Definicja 1.1

Ustalmy funkcje \displaystyle t,s:\mathbb{N}\rightarrow \mathbb{N}. Mówimy, że maszyna Turinga \displaystyle \mathcal{MT} (deterministyczna lub niedeterministyczna) akceptuje słowo \displaystyle w\in \Sigma_I^* w czasie \displaystyle t(|w|), jeśli istnieje ciąg \displaystyle k\leqslant t(|w|) konfiguracji \displaystyle d_1,d_2,\dots, d_k takich, że \displaystyle d_1=\sharp s_0 w \sharp, \displaystyle d_k= \sharp w_{1}s_{F}w_{2}\sharp dla pewnych \displaystyle w_{1},w_{2}\in \Sigma _{T}^{*},s_{F}\in S_{F} oraz \displaystyle d_i \mapsto d_{i+1} dla \displaystyle i=1,\dots,k-1.

Jeśli istnieje ciąg konfiguracji \displaystyle d_1 \mapsto d_2 \mapsto \dots \mapsto d_m, gdzie \displaystyle d_1=\sharp s_0 w \sharp, \displaystyle d_m jest konfiguracją akceptującą (tzn. \displaystyle d_m= \sharp w_{1}s_{F}w_{2}\sharp dla pewnych \displaystyle w_{1},w_{2}\in \Sigma _{T}^{*},s_{F}\in S_{F}) oraz dodatkowo \displaystyle |d_i|\leqslant s(|w|)+2, to mówimy, że maszyna \displaystyle \mathcal{MT} akceptuje słowo \displaystyle w\in \Sigma_I^* w pamięci \displaystyle s(|w|).

Mówimy, że język \displaystyle L jest akceptowany w czasie \displaystyle t(n) (pamięci \displaystyle s(n)), jeśli istnieje maszyna Turinga \displaystyle \mathcal{MT}, dla której \displaystyle L(\mathcal{MT})=L oraz każde słowo \displaystyle w\in L jest akceptowane w czasie \displaystyle t(|w|) (pamięci \displaystyle s(|w|) odpowiednio).

Uwaga 1.1

W niektórych podejściach wykorzystuje się, do definicji złożoności pamięciowej, tak zwanych maszyn Turinga off-line. Pomysł polega na tym, aby nie uwzględniać komórek taśmy, z których maszyna czytała informacje, a jedynie te, do których następował zapis. Dzięki temu zabiegowi można w sposób "rozsądny" mówić o akceptacji słowa w pamięci \displaystyle \log n itp. W ujęciu prezentowanym w tym wykładzie zajmujemy się akceptacją w pamięci \displaystyle n^k, dla \displaystyle k\geqslant 1, zatem nie ma potrzeby dodatkowego definiowania maszyn Turinga off-line.

Definicja 1.2

Oznaczmy przez \displaystyle Dtime(t(n)) oraz \displaystyle Dspace(s(n)) rodzinę języków akceptowanych w czasie \displaystyle t(n) i odpowiednio pamięci \displaystyle s(n) przez deterministyczną maszynę Turinga. Dla maszyn niedeterministycznych wprowadzamy w identyczny sposób klasy \displaystyle Ntime(t(n)) oraz \displaystyle Nspace(s(n)).

Określamy następujące klasy złożoności (klasy języków):

\displaystyle \aligned  \textbd{P} \displaystyle  =\bigcup_{k=0}^\infty Dtime(n^k), &\qquad\qquad& \textbd{NP} \displaystyle  =\bigcup_{k=0}^\infty Ntime(n^k), \\ \textbd{PSPACE} \displaystyle  =\bigcup_{k=0}^\infty Dspace(n^k), && \textbd{NSPACE} \displaystyle  =\bigcup_{k=0}^\infty Nspace(n^k). \endaligned

Wprost z definicji otrzymujemy zależności P \displaystyle  \subset NP oraz PSPACE \displaystyle  \subset NPSPACE . W dalszej części wykładu udowodnimy kilka mniej oczywistych zależności.

Przykład 1.1

Rozważmy język:

\displaystyle  L=\left\{1^i 2^j 3^k\: k=i\cdot j,\: i,j\geqslant 1\right\}.

Język \displaystyle L\in P . Deterministyczna maszyna Turinga \displaystyle MT_3 akceptująca taki język może wyglądać następująco (zaczynamy od konfiguracji \displaystyle \sharp s_0 w \sharp):

  1. Jeśli symbol pod głowicą, to \displaystyle 1 zamień go na \displaystyle\sharp. Inaczej odrzuć.
  2. Przejdź od lewego ogranicznika do prawego, sprawdzając, czy po \displaystyle 1 występuje \displaystyle 1 lub \displaystyle 2, po \displaystyle 2 tylko \displaystyle 2 lub \displaystyle 3, a po \displaystyle 3 kolejny symbol \displaystyle 3 lub ogranicznik. Jeśli ta zależność nie jest spełniona, odrzuć. Gdy osiągniesz ogranicznik wykonaj następny krok.
  3. Gdy przed ogranicznikiem nie znajduje się symbol \displaystyle 3, odrzuć. W przeciwnym razie zamień symbol \displaystyle 3 na \displaystyle \sharp, a następnie poruszaj się w lewo, aż dotrzesz do symbolu innego niż \displaystyle 3 i \displaystyle \diamondsuit.
  4. Jeśli symbol do którego dotarłeś to \displaystyle 2, zamień go na \displaystyle \diamondsuit. Sprawdź symbol po lewej. Jeśli to \displaystyle 2, poruszaj się w prawo aż do ogranicznika. Następnie przejdź do kroku 3.
  5. Jeśli dotarłeś do symbolu \displaystyle 1, poruszaj się w lewo aż do ogranicznika. Zamień symbol \displaystyle 1 przy ograniczniku na \displaystyle \sharp, a następnie idź w prawo, zamieniając wszystkie symbole \displaystyle \diamondsuit na \displaystyle 2. Gdy dojdziesz do ogranicznika, przejdź do kroku \displaystyle 3.
  6. Jeśli dotarłeś do ogranicznika, oznacza to, że skasowano już wszystkie symbole \displaystyle 1. Przejdź w prawo aż do ogranicznika. Jeśli natrafisz na symbol \displaystyle 3, odrzuć. W przeciwnym przypadku, akceptuj.

Nietrudno zaobserwować, że maszyna \displaystyle MT_3 przechodzi przez taśmę w prawo i w lewo tyle razy, ile symboli \displaystyle 3 zawiera taśma oraz wykonuje jeden dodatkowy przebieg na starcie. Zatem słowa z \displaystyle L są akceptowane w czasie ograniczonym wielomianowo.

Przykład 1.2

Rozważmy teraz język

\displaystyle  L=\left\{3^k\: : \: k=i\cdot j dla pewnych \displaystyle   i,j> 1\rbrace.

Najprostszą metodą uzasadnienia, że \displaystyle L\in NP jest konstrukcja tak zwanej wyroczni. Polega ona na następującej dwuetapowej procedurze:

  1. Skonstruuj niedeterministyczną maszynę Turinga (wyrocznia) generującą pewne słowo (certyfikat).
  2. Zweryfikuj w sposób deterministyczny spełnienie założeń przez certyfikat.

W naszym przykładzie Etap 1 wygląda następująco:

  1. Użyj dwóch taśm. Na pierwszej z nich znajduje się \displaystyle 3^k.
  2. Idź po pierwszej taśmie, wykorzystując niedeterministyczną funkcję przejść. Napotykając \displaystyle 3, możesz wypisać \displaystyle 1 na taśmie drugiej i przejść o jedną komórkę w prawo na taśmie pierwszej lub przejść do następnego kroku. Jeśli dotarłeś do prawego ogranicznika taśmy pierwszej, przejdź do kroku 3.
  3. Powróć do początku pierwszej taśmy. Wykonaj sekwencję jak w kroku \displaystyle 2, z tą różnicą, że teraz na drugiej taśmie wypisuj symbole \displaystyle 2.
  4. Jako ostatnią część tego etapu przekopiuj symbole \displaystyle 3 z pierwszej taśmy na drugą (po symbolach \displaystyle 1 i \displaystyle 2).

W konstrukcji wykorzystaliśmy dwie taśmy, ale oczywiście w nawiązaniu do wcześniejszych uwag, całą konstrukcję można wykonać na jednej taśmie (z odpowiednio rozszerzonym alfabetem i bardziej skomplikowaną funkcją przejść).

Etap 2 polega na weryfikacji, czy na taśmie drugiej znajduje się słowo postaci \displaystyle 1^i 2^j 3^k, gdzie \displaystyle i,j>1 oraz \displaystyle k=i\cdot j. Jeśli tak, to słowo wejściowe \displaystyle 3^k pochodziło z języka \displaystyle L i akceptujemy. Można do tego wykorzystać deterministyczną maszynę Turinga, niemal identyczną z opisaną w przykładzie poprzednim.

Jeśli słowo wejściowe pochodzi z języka \displaystyle L, to jedno z obliczeń maszyny niedeterministycznej z Etapu 1. prowadzi do konstrukcji odpowiedniego słowa na drugiej taśmie. Nie wiemy, jaka dokładnie ścieżka obliczeń ma być wykorzystana, ale dla akceptacji języka \displaystyle L nie ma to znaczenia.

Zastanów się, czy da się wykazać, że także \displaystyle L\in P (Ćwiczenie 1.3, do tego wykładu).

Definicja 1.3

Funkcja \displaystyle s(n) jest konstruowalna pamięciowo, jeśli istnieje maszyna Turinga \displaystyle \mathcal{MT}=(\Sigma _{T},S,f,s_{0},S_{F}), dla której \displaystyle d_1 \mapsto^* d_2, gdzie \displaystyle d_1=\sharp s_0 1^n \sharp, \displaystyle d_2=\sharp s_1 1^{s(n)} w \sharp dla \displaystyle s_1\in S_F, \displaystyle w\in (\Sigma_T\setminus \left\{1\right\})^* oraz dodatkowo \displaystyle d_2 jest konfiguracją końcową.

Inaczej mówiąc, funkcję \displaystyle s(n) nazywamy konstruowalną pamięciowo, jeśli istnieje maszyna Turinga \displaystyle \mathcal{MT}, otrzymując na wejściu słowo \displaystyle w długości \displaystyle |w|=n, zaznacza na taśmie roboczej \displaystyle s(n) klatek i zatrzymuje się (akceptując słowo \displaystyle w).

Przykład 1.3

Funkcja \displaystyle s(n)=2n jest konstruowalna pamięciowo. Maszyna \displaystyle MT_4, która konstruuje \displaystyle s(n) działa według schematu:

  1. Przejdź do prawego markera. Jeśli napotkano symbol inny niż \displaystyle 1, to odrzuć.
  2. Idź w lewo aż do pierwszego symbolu \displaystyle 1 lub markera \displaystyle \sharp
  3. Jeśli napotkałeś symbol \displaystyle 1, zamień go na \displaystyle \clubsuit i przejdź do prawego markera. Dopisz do słowa symbol \displaystyle \clubsuit (zwiększając tym samym długość słowa na taśmie o \displaystyle 1). Następnie powtórz cykl od \displaystyle 2.
  4. Jeśli napotkałeś marker, idź w prawo, zamieniając wszystkie wystąpienia \displaystyle \clubsuit na \displaystyle 1. Następnie wracaj do lewego markera i zatrzymaj się, akceptując.

Twierdzenie 1.1 liniowa kompresja pamięci

Niech będzie dany język \displaystyle L oraz maszyna Turinga \displaystyle \mathcal{TM} akceptująca \displaystyle L w pamięci \displaystyle s(n). Dla dowolnego \displaystyle \varepsilon>0 istnieje maszyna Turinga \displaystyle \mathcal{TM}' akceptująca \displaystyle L w pamięci \displaystyle \max\left\{n,\varepsilon s(n)\right\}.

Dowód

(Szkic) Ustalamy liczbę naturalną \displaystyle k, dla której \displaystyle \varepsilon k\geqslant 2. Maszynę \displaystyle \mathcal{TM}' definiujemy następująco:

  1. Przekoduj słowo wejściowe, łącząc po \displaystyle r kolejnych symboli w jeden blok stanowiący nowy symbol na taśmie.
  2. Symuluj maszynę \displaystyle \mathcal{MT} na skompresowanej taśmie. Położenie głowicy wewnątrz bloku zakoduj w stanach maszyny \displaystyle \mathcal{MT}'.

Zauważmy, że w kroku \displaystyle 1. maszyna \displaystyle \mathcal{MT}' wykorzystuje \displaystyle n komórek pamięci do odczytania słowa wejściowego. Kompresja taśmy zapewnia, że podczas symulowania maszyny \displaystyle \mathcal{MT} nie wykorzystamy więcej niż \displaystyle \lceil \frac{s(n)}{k}\rceil \leqslant \varepsilon s(n) komórek. Jednocześnie można założyć, że \displaystyle \mathcal{MT}' akceptuje słowa wejściowe z języka \displaystyle L o długości mniejszej niż \displaystyle k bez symulowania \displaystyle \mathcal{MT}.

image:End_of_proof.gif

Twierdzenie 1.2 Savitch

Dla dowolnej funkcji \displaystyle s(n) konstruowalnej pamięciowo spełniającej warunek \displaystyle s(n)\geqslant \log_2 n prawdziwa jest inkluzja \displaystyle Nspace(s(n))\subset DSpace(s^2(n)).

Dowód

Niech \displaystyle \mathcal{NMT} będzie niedeterministyczną maszyną Turinga akceptującą język \displaystyle L=L(\mathcal{NMT}) w pamięci \displaystyle s(n). Niech \displaystyle k(n) oznacza liczbę konfiguracji potrzebną do zaakceptowania słowa o długości \displaystyle n. Istnieje liczba \displaystyle c>1, dla której \displaystyle k(n)\leqslant c^{s(n)}, co z kolei oznacza, że każde słowo o długości \displaystyle n jest akceptowane w \displaystyle c^{s(n)} krokach czasowych.

image:End_of_proof.gif

Rozważmy algorytm:

Algorytm


  1  Wejście: słowo \displaystyle w długości \displaystyle |w|=n
  2  oblicz \displaystyle s(n)
  3  for każda konfiguracja akceptująca \displaystyle d_A dla której \displaystyle |d_A|\leqslant s(n)
  4    do if Test(\displaystyle \sharp s_0 w \sharp, \displaystyle d_A, \displaystyle s(n) \log_2 c) then akceptuj

gdzie procedura Test ma następującą postać:

Algorytm Procedure Test(\displaystyle d,\displaystyle d',\displaystyle i)


  1  if \displaystyle i=0 and [ (\displaystyle d=d') or (\displaystyle d\mapsto d')] then return true
  2    else for każda konfiguracja \displaystyle d'' dla której \displaystyle |d''|\leqslant s(n)
  3      do if Test(\displaystyle d,\displaystyle d'',\displaystyle i-1) and Test \displaystyle d'',\displaystyle d',\displaystyle i-1)
  4        then return true;
  5  return false

Przedstawiony algorytm można zrealizować za pomocą wielotaśmowej maszyny Turinga. Założenie dotyczące konstruowalności pamięciowej jest istotnie wykorzystywane w tej konstrukcji przy implementacji linii 3 algorytmu i linii 2 procedury Test. Musimy zaznaczyć \displaystyle s(n) komórek taśmy, aby móc konstruować konfiguracje o długości ograniczonej przez \displaystyle s(n) i móc następnie wykonywać na nich symulację maszyny \displaystyle \mathcal{NMT}.

Zauważmy, że ilość konfiguracji jest ograniczona przez \displaystyle s(n), a głębokość rekursji przez \displaystyle \log c^{s(n)}. Oznacza to, że jesteśmy w stanie skonstruować maszynę Turinga, która wymaga \displaystyle c' s^2(n) pamięci, gdzie \displaystyle c' jest pewną stałą. Na mocy Twierdzenia 1.1 jesteśmy w stanie określić maszynę \displaystyle \mathcal{MT} działającą w pamięci \displaystyle s^2(n).

Wniosek 1.1

PSPACE \displaystyle  = NPSPACE

Lemat 1.1

Jeśli \displaystyle g(n)\geqslant n, to \displaystyle Dtime(g(n))\subset Dspace(g(n)) oraz \displaystyle Ntime(g(n))\subset Nspace(g(n)).

Dowód

Niech będzie dana maszyna deterministyczna \displaystyle \mathcal{MT} akceptująca dany język \displaystyle L w czasie \displaystyle g(n). Do akceptacji słowa \displaystyle w o długości \displaystyle n maszyna wykorzystuje co najwyżej \displaystyle g(n) kroków czasowych, czyli odwiedza co najwyżej \displaystyle g(n)+1 komórek taśmy.

Na podstawie Twierdzenia 1.1 istnieje maszyna Turinga \displaystyle \mathcal{MT}' wykorzystująca

\displaystyle  \max \left\{n, \frac{1}{2}(g(n)+1)\right\}\leqslant g(n)

komórek pamięci. Dla niedeterministycznych maszyn Turinga argumentacja jest identyczna.

image:End_of_proof.gif

Wniosek 1.2

P \displaystyle  \subset NP \displaystyle  \subset PSPACE \displaystyle  = NPSPACE
Uwaga 1.2

Nie jest znany przykład wykazujący silną inkluzję P \displaystyle  \varsubsetneq NP ani dowód wykluczający istnienie takiego przykładu. Powszechnie uznawana hipoteza głosi:

P \displaystyle  \neq NP.

Rozstrzygnięcie jej prawdziwości lub fałszywości stanowi jeden z najważniejszych, a zarazem najtrudniejszych problemów współczesnej informatyki. Jak widzieliśmy w Przykładzie 1.2, nawet w przypadku konkretnego języka \displaystyle L\in NP, problem uzasadnienia, że także \displaystyle L\in P, jest nietrywialny, gdyż wymaga zazwyczaj konstrukcji całkiem nowej maszyny Turinga niż ta do weryfikacji \displaystyle L\in NP .

Redukcja i problemy zupełne

Definicja 2.1 transformacja wielomianowa

Niech \displaystyle L_1,L_2 będą dowolnymi językami nad pewnym alfabetem \displaystyle \Sigma_I. Mówimy, że \displaystyle L_1 redukuje się do \displaystyle L_2 w czasie wielomianowym, co oznaczamy \displaystyle L_1 \propto L_2, gdy istnieje deterministyczna maszyna Turinga \displaystyle \mathcal{MT}=(\Sigma _{T},S,f,s_{0},S_{F}) taka, że dla dowolnego \displaystyle w\in \Sigma_I^* istnieje \displaystyle w'\in \Sigma_I^* i stan \displaystyle s_1\in S_F o własności

\displaystyle  \sharp s_0 w \sharp \mapsto^* \sharp s_1 w' \sharp

oraz

\displaystyle  w\in L_1 \quad \Longleftrightarrow \quad w' \in L_2.

Lemat 2.1

Załóżmy, że \displaystyle L_1 \propto L_2. Wtedy zachodzą implikacje:

  1. \displaystyle L_2 \in P      \displaystyle \quad \Longrightarrow \quad L_1 \in P,
  2. \displaystyle L_2 \in NP      \displaystyle \quad \Longrightarrow \quad L_1 \in NP,
  3. \displaystyle L_2 \in PSPACE      \displaystyle \quad \Longrightarrow \quad L_1 \in PSPACE.

Dowód

Dane słowo \displaystyle w transformujemy do \displaystyle w' w czasie wielomianowym, co gwarantuje założenie \displaystyle L_1 \propto L_2. Dzięki założeniu \displaystyle L_2 \in P możemy rozstrzygnąć, czy \displaystyle w'\in L_2 (tzn. jeśli akceptujemy \displaystyle w', to robimy to w czasie wielomianowym). Tym sposobem (korzystając z definicji transformacji wielomianowej) akceptujemy \displaystyle w w czasie wielomianowym, o ile tylko \displaystyle w\in L_1. Dowód dla pozostałych implikacji jest identyczny.

image:End_of_proof.gif

Definicja 2.2

Niech \displaystyle \mathcal{C} oznacza pewną klasę języków. Język \displaystyle L nazywamy \displaystyle \mathcal{C}-trudnym, jeśli spełniony jest warunek:

\displaystyle  \forall\; L' \in \mathcal{C} \quad L'\propto L.

Jeżeli dodatkowo spełniony jest warunek \displaystyle L\in \mathcal{C}, to język \displaystyle L nazywamy \displaystyle \mathcal{C}-zupełnym.

Intuicyjnie, fakt, że język jest \displaystyle \mathcal{C}-zupełny, oznacza, że jest on najbardziej skomplikowany (pod względem obliczeniowym) wśród języków z klasy \displaystyle \mathcal{C}, natomiast język \displaystyle \mathcal{C}-trudny jest bardziej skomplikowany niż każdy z klasy \displaystyle \mathcal{C}, choć sam nie musi do niej należeć.

Uwaga 2.1

Rozważając klasę P , NP i PSPACE, możemy mówić o językach (problemach) P -zupełnych, NP -zupełnych, czy też PSPACE -zupełnych. To samo odnosi się do języków trudnych (tzn. klasa języków P -trudnych, itd.).

Przykład 2.1

Rozważmy języki:

\displaystyle  L_1=\left\{1^i 2^j 3^k\: k=i\cdot j,\: i,j\geqslant 1\right\}\quad,\quad L_2=\left\{1^i 2^j 4^{2k}\: k=i\cdot j,\: i,j\geqslant 1\right\}.

Języki: \displaystyle L_1 oraz \displaystyle L_2 wyglądają na bardzo podobne, zatem wydaje się, że \displaystyle L_1 \propto L_2 oraz \displaystyle L_2 \propto L_1. Uzasadnienie tego faktu jest prawie natychmiastowe.

Konstruujemy deterministyczną maszynę Turinga która działa w następujący sposób:

  1. Jeśli słowo wejściowe jest puste, to stop.
  2. Przejdź do prawego ogranicznika. Jeśli przy ograniczniku nie występuje symbol \displaystyle 4, to wykonaj krok 1.
  3. Jeśli w słowie wejściowym występuje symbol \displaystyle 4, to sprawdź, czy słowo przetwarzane jest postaci \displaystyle \sharp w 4^s \sharp, gdzie \displaystyle s\geqslant 1 oraz \displaystyle w\in (\Sigma_I\setminus \left\{4\right\})^* oraz czy dodatkowo \displaystyle s jest liczbą parzystą. Jeśli nie, to wykonaj krok 1.
  4. Zamień słowo \displaystyle 4^s na słowo \displaystyle 3^{\frac{s}{2}}\sharp^{\frac{s}{2}} i wykonaj krok 1.
  5. Przejdź nad pierwszy symbol po lewym ograniczniku i zatrzymaj się.

W ten sposób zawsze przeprowadzamy konfigurację \displaystyle \sharp s_0 w \sharp na konfigurację \displaystyle \sharp s_1 w' \sharp, przy czym \displaystyle w'=1^i 2^j 3^k tylko, gdy \displaystyle w=1^i 2^j 4^{2k}. Zatem \displaystyle w\in L_2 wtedy i tylko wtedy, gdy \displaystyle w'\in L_1. Wykazaliśmy, że \displaystyle L_2 \propto L_1.

Warunek \displaystyle L_1 \propto L_2 otrzymujemy w sposób identyczny. Trzeba tylko wypisać odpowiednią ilość symboli \displaystyle 4 (a wiemy już, jak konstruować liczbę \displaystyle 2n, mając dane \displaystyle n).