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

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.

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 $t,s:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$. Mówimy, że maszyna Turinga ${ℳ}{𝒯}$ (deterministyczna lub niedeterministyczna) akceptuje słowo $w\in {\mathrm{\Sigma }}_I^{*}$ w czasie $t(|w|)$, jeśli istnieje ciąg $k⩽t(|w|)$ konfiguracji $d_1,d_2,\dots ,d_k$ takich, że $d_1=\mathrm{♯}{s}_{0}w\mathrm{♯}$, $d_k=\mathrm{♯}{w}_1{s}_F{w}_2\mathrm{♯}$ dla pewnych $w_1,w_2\in {\mathrm{\Sigma }}_T^{*},s_F\in S_F$ oraz $d_i\mapsto d_{i+1}$ dla $i=1,\dots ,k-1$.

Jeśli istnieje ciąg konfiguracji $d_1\mapsto d_2\mapsto \dots \mapsto d_m$, gdzie $d_1=\mathrm{♯}{s}_{0}w\mathrm{♯}$, $d_m$ jest konfiguracją akceptującą (tzn. $d_m=\mathrm{♯}{w}_1{s}_F{w}_2\mathrm{♯}$ dla pewnych $w_1,w_2\in {\mathrm{\Sigma }}_T^{*},s_F\in S_F$) oraz dodatkowo $|d_i|⩽s(|w|)+2$, to mówimy, że maszyna ${ℳ}{𝒯}$ akceptuje słowo $w\in {\mathrm{\Sigma }}_I^{*}$ w pamięci $s(|w|)$.

Mówimy, że język $L$ jest akceptowany w czasie $t(n)$ (pamięci $s(n)$), jeśli istnieje maszyna Turinga ${ℳ}{𝒯}$, dla której $L({ℳ}{𝒯})=L$ oraz każde słowo $w\in L$ jest akceptowane w czasie $t(|w|)$ (pamięci $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 $\log n$ itp. W ujęciu prezentowanym w tym wykładzie zajmujemy się akceptacją w pamięci $n^k$, dla $k⩾1$, zatem nie ma potrzeby dodatkowego definiowania maszyn Turinga off-line.

Definicja 1.2

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

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

$\begin{array}{rlr}\mathbf{𝐏}=\bigcup _{k=0}^{\mathrm{\infty }}Dtime(n^k),& & \mathbf{𝐍}\mathbf{𝐏}=\bigcup _{k=0}^{\mathrm{\infty }}Ntime(n^k),\\ \mathbf{𝐏}\mathbf{𝐒}\mathbf{𝐏}\mathbf{𝐀}\mathbf{𝐂}\mathbf{𝐄}=\bigcup _{k=0}^{\mathrm{\infty }}Dspace(n^k),& & \mathbf{𝐍}\mathbf{𝐒}\mathbf{𝐏}\mathbf{𝐀}\mathbf{𝐂}\mathbf{𝐄}=\bigcup _{k=0}^{\mathrm{\infty }}Nspace(n^k).\end{array}$

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

Przykład 1.1

Rozważmy język:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle L = \left\{1^i 2^j 3^k: k=i\cdot j,: i,j\geqslant 1\}\right}

Język $L\in$ P . Deterministyczna maszyna Turinga $M{T}_3$ akceptująca taki język może wyglądać następująco (zaczynamy od konfiguracji $\mathrm{♯}{s}_{0}w\mathrm{♯}$):

1. Jeśli symbol pod głowicą, to $1$ zamień go na $\mathrm{♯}$. Inaczej odrzuć.
2. Przejdź od lewego ogranicznika do prawego, sprawdzając, czy po $1$ występuje $1$ lub $2$, po $2$ tylko $2$ lub $3$, a po $3$ kolejny symbol $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 $3$, odrzuć. W przeciwnym razie zamień symbol $3$ na $\mathrm{♯}$, a następnie poruszaj się w lewo, aż dotrzesz do symbolu innego niż $3$ i $\mathrm{♢}$.
4. Jeśli symbol do którego dotarłeś to $2$, zamień go na $\mathrm{♢}$. Sprawdź symbol po lewej. Jeśli to $2$, poruszaj się w prawo aż do ogranicznika. Następnie przejdź do kroku 3.
5. Jeśli dotarłeś do symbolu $1$, poruszaj się w lewo aż do ogranicznika. Zamień symbol $1$ przy ograniczniku na $\mathrm{♯}$, a następnie idź w prawo, zamieniając wszystkie symbole $\mathrm{♢}$ na $2$. Gdy dojdziesz do ogranicznika, przejdź do kroku $3$.
6. Jeśli dotarłeś do ogranicznika, oznacza to, że skasowano już wszystkie symbole $1$. Przejdź w prawo aż do ogranicznika. Jeśli natrafisz na symbol $3$, odrzuć. W przeciwnym przypadku, akceptuj.

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

Przykład 1.2

Rozważmy teraz język

$L=\{3^k:k=i\cdot j\text{ dla pewnych }i,j>1\}$

Najprostszą metodą uzasadnienia, że $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ę $3^k$.
2. Idź po pierwszej taśmie, wykorzystując niedeterministyczną funkcję przejść. Napotykając $3$, możesz wypisać $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 $2$, z tą różnicą, że teraz na drugiej taśmie wypisuj symbole $2$.
4. Jako ostatnią część tego etapu przekopiuj symbole $3$ z pierwszej taśmy na drugą (po symbolach $1$ i $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 $1^i{2}^j{3}^k$, gdzie $i,j>1$ oraz $k=i\cdot j$. Jeśli tak, to słowo wejściowe $3^k$ pochodziło z języka $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 $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 $L$ nie ma to znaczenia.

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

Definicja 1.3

Funkcja $s(n)$ jest konstruowalna pamięciowo, jeśli istnieje maszyna Turinga ${ℳ}{𝒯}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$, dla której $d_1{\mapsto }^{*}{d}_2$, gdzie $d_1=\mathrm{♯}{s}_0{1}^n\mathrm{♯}$, $d_2=\mathrm{♯}{s}_1{1}^{s(n)}w\mathrm{♯}$ dla $s_1\in S_F$, $w\in ({\mathrm{\Sigma }}_T\setminus \left\{1\right\}{)}^{*}$ oraz dodatkowo $d_2$ jest konfiguracją końcową.

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

Przykład 1.3

Funkcja $s(n)=2n$ jest konstruowalna pamięciowo. Maszyna $M{T}_4$, która konstruuje $s(n)$ działa według schematu:

1. Przejdź do prawego markera. Jeśli napotkano symbol inny niż $1$, to odrzuć.
2. Idź w lewo aż do pierwszego symbolu $1$ lub markera $\mathrm{♯}$
3. Jeśli napotkałeś symbol $1$, zamień go na $\mathrm{♣}$ i przejdź do prawego markera. Dopisz do słowa symbol $\mathrm{♣}$ (zwiększając tym samym długość słowa na taśmie o $1$). Następnie powtórz cykl od $2$.
4. Jeśli napotkałeś marker, idź w prawo, zamieniając wszystkie wystąpienia $\mathrm{♣}$ na $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 $L$ oraz maszyna Turinga ${𝒯}{ℳ}$ akceptująca $L$ w pamięci $s(n)$. Dla dowolnego $\epsilon >0$ istnieje maszyna Turinga ${{𝒯}{ℳ}}^{\prime }$ akceptująca $L$ w pamięci $\max \{n,\epsilon s(n)\}$.

Dowód

(Szkic) Ustalamy liczbę naturalną $k$, dla której $\epsilon k⩾2$. Maszynę ${{𝒯}{ℳ}}^{\prime }$ definiujemy następująco:

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

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

Twierdzenie 1.2 Savitch

Dla dowolnej funkcji $s(n)$ konstruowalnej pamięciowo spełniającej warunek $s(n)⩾{\log }_{2}n$ prawdziwa jest inkluzja $Nspace(s(n))\subset DSpace(s^2(n))$.

Dowód

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

Rozważmy algorytm:

Algorytm

---

  1  Wejście: słowo $w$ długości $|w|=n$
  2  oblicz $s(n)$
  3  for każda konfiguracja akceptująca $d_A$ dla której $|d_A|⩽s(n)$
  4    do if Test($\mathrm{♯}{s}_{0}w\mathrm{♯}$, $d_A$, $s(n){\log }_{2}c$) then akceptuj

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

Algorytm Procedure Test($d$,$d^{\prime }$,$i$)

---

  1  if $i=0$ and [ ($d=d^{\prime }$) or ($d\mapsto d^{\prime }$)] then return true
  2    else for każda konfiguracja $d^{″}$ dla której $|d^{″}|⩽s(n)$
  3      do if Test($d$,$d^{″}$,$i-1$) and Test $d^{″}$,$d^{\prime }$,$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ć $s(n)$ komórek taśmy, aby móc konstruować konfiguracje o długości ograniczonej przez $s(n)$ i móc następnie wykonywać na nich symulację maszyny ${𝒩}{ℳ}{𝒯}$.

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

Wniosek 1.1

PSPACE $=$ NPSPACE

Lemat 1.1

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

Dowód

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

Na podstawie Twierdzenia 1.1 istnieje maszyna Turinga ${{ℳ}{𝒯}}^{\prime }$ wykorzystująca

$\max \{n,\frac{1}{2}(g(n)+1)\}⩽g(n)$

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

Wniosek 1.2

P $\subset$ NP $\subset$ PSPACE $=$ NPSPACE

Uwaga 1.2

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

P $\ne$ 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 $L\in$ NP, problem uzasadnienia, że także $L\in$ P, jest nietrywialny, gdyż wymaga zazwyczaj konstrukcji całkiem nowej maszyny Turinga niż ta do weryfikacji $L\in$ NP .

Redukcja i problemy zupełne

Definicja 2.1 transformacja wielomianowa

Niech $L_1,L_2$ będą dowolnymi językami nad pewnym alfabetem ${\mathrm{\Sigma }}_I$. Mówimy, że $L_1$ redukuje się do $L_2$ w czasie wielomianowym, co oznaczamy $L_1\propto L_2$, gdy istnieje deterministyczna maszyna Turinga ${ℳ}{𝒯}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$ taka, że dla dowolnego $w\in {\mathrm{\Sigma }}_I^{*}$ istnieje $w^{\prime }\in {\mathrm{\Sigma }}_I^{*}$ i stan $s_1\in S_F$ o własności

$\mathrm{♯}{s}_{0}w\mathrm{♯}{\mapsto }^{*}\mathrm{♯}{s}_1{w}^{\prime }\mathrm{♯}$

oraz

$w\in L_1⟺w^{\prime }\in L_2$

Lemat 2.1

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

1. $L_2\in$ P      $⟹L_1\in$ P,
2. $L_2\in$ NP      $⟹L_1\in$ NP,
3. $L_2\in$ PSPACE      $⟹L_1\in$ PSPACE.

Dowód

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

Definicja 2.2

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

$\mathrm{\forall }{L}^{\prime }\in {𝒞}{L}^{\prime }\propto L$

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

Intuicyjnie, fakt, że język jest ${𝒞}$-zupełny, oznacza, że jest on najbardziej skomplikowany (pod względem obliczeniowym) wśród języków z klasy ${𝒞}$, natomiast język ${𝒞}$-trudny jest bardziej skomplikowany niż każdy z klasy ${𝒞}$, 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:

$L_1=\{1^i{2}^j{3}^k:k=i\cdot j,:i,j⩾1\},L_2=\{1^i{2}^j{4}^{2k}:k=i\cdot j,:i,j⩾1\}$

Języki: $L_1$ oraz $L_2$ wyglądają na bardzo podobne, zatem wydaje się, że $L_1\propto L_2$ oraz $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 $4$, to wykonaj krok 1.
3. Jeśli w słowie wejściowym występuje symbol $4$, to sprawdź, czy słowo przetwarzane jest postaci $\mathrm{♯}w{4}^s\mathrm{♯}$, gdzie $s⩾1$ oraz $w\in ({\mathrm{\Sigma }}_I\setminus \left\{4\right\}{)}^{*}$ oraz czy dodatkowo $s$ jest liczbą parzystą. Jeśli nie, to wykonaj krok 1.
4. Zamień słowo $4^s$ na słowo $3^{\frac{s}{2}}{\mathrm{♯}}^{\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ę $\mathrm{♯}{s}_{0}w\mathrm{♯}$ na konfigurację $\mathrm{♯}{s}_1{w}^{\prime }\mathrm{♯}$, przy czym $w^{\prime }=1^i{2}^j{3}^k$ tylko, gdy $w=1^i{2}^j{4}^{2k}$. Zatem $w\in L_2$ wtedy i tylko wtedy, gdy $w^{\prime }\in L_1$. Wykazaliśmy, że $L_2\propto L_1$.

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