|
|
| (Nie pokazano 78 pośrednich wersji utworzonych przez tego samego użytkownika) |
| Linia 1: |
Linia 1: |
| Sformułujemy definicje podstawowych klas
| | 5555555555555555555555555555555555555555 Logika |
| 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.
| |
|
| |
|
| __FORCETOC__
| |
|
| |
|
| ==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||
| | 10101010101010101010101010101010101010101010101010 Logika |
| Ustalmy funkcje <math>\displaystyle t,s:\mathbb{N}\rightarrow \mathbb{N}</math>. Mówimy, że
| |
| maszyna Turinga <math>\displaystyle \mathcal{MT}</math> (deterministyczna lub
| |
| niedeterministyczna) '''akceptuje słowo <math>\displaystyle w\in \Sigma_I^*</math> w
| |
| czasie <math>\displaystyle t(|w|)</math>''', jeśli istnieje ciąg <math>\displaystyle k\leqslant t(|w|)</math> konfiguracji
| |
| <math>\displaystyle d_1,d_2,\dots, d_k</math> takich, że <math>\displaystyle d_1=\sharp s_0 w \sharp</math>, <math>\displaystyle d_k=
| |
| \sharp w_{1}s_{F}w_{2}\sharp</math> dla pewnych <math>\displaystyle w_{1},w_{2}\in \Sigma
| |
| _{T}^{*},s_{F}\in S_{F}</math> oraz <math>\displaystyle d_i \mapsto d_{i+1}</math> dla
| |
| <math>\displaystyle i=1,\dots,k-1</math>.
| |
| | |
| Jeśli istnieje ciąg konfiguracji <math>\displaystyle d_1 \mapsto d_2 \mapsto \dots
| |
| \mapsto d_m</math>, gdzie <math>\displaystyle d_1=\sharp s_0 w \sharp</math>, <math>\displaystyle d_m</math> jest
| |
| konfiguracją akceptującą (tzn. <math>\displaystyle d_m= \sharp w_{1}s_{F}w_{2}\sharp</math>
| |
| dla pewnych <math>\displaystyle w_{1},w_{2}\in \Sigma _{T}^{*},s_{F}\in S_{F}</math>) oraz
| |
| dodatkowo <math>\displaystyle |d_i|\leqslant s(|w|)+2</math>, to mówimy, że maszyna <math>\displaystyle \mathcal{MT}</math>
| |
| '''akceptuje słowo <math>\displaystyle w\in \Sigma_I^*</math> w pamięci <math>\displaystyle s(|w|)</math>'''.
| |
| | |
| Mówimy, że '''język <math>\displaystyle L</math> jest akceptowany w czasie <math>\displaystyle t(n)</math>
| |
| (pamięci <math>\displaystyle s(n)</math>)''', jeśli istnieje maszyna Turinga <math>\displaystyle \mathcal{MT}</math>, dla
| |
| której <math>\displaystyle L(\mathcal{MT})=L</math> oraz każde słowo <math>\displaystyle w\in L</math> jest
| |
| akceptowane w czasie <math>\displaystyle t(|w|)</math> (pamięci <math>\displaystyle s(|w|)</math> 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 <math>\displaystyle \log n</math> itp. W ujęciu prezentowanym w tym wykładzie
| |
| zajmujemy się akceptacją w pamięci <math>\displaystyle n^k</math>, dla <math>\displaystyle k\geqslant 1</math>, zatem nie ma
| |
| potrzeby dodatkowego definiowania maszyn Turinga off-line.
| |
| }}
| |
| | |
| {{definicja|1.2||
| |
| Oznaczmy przez <math>\displaystyle Dtime(t(n))</math> oraz <math>\displaystyle Dspace(s(n))</math> rodzinę języków
| |
| akceptowanych w czasie <math>\displaystyle t(n)</math> i odpowiednio pamięci <math>\displaystyle s(n)</math> przez
| |
| deterministyczną maszynę Turinga. Dla maszyn niedeterministycznych
| |
| wprowadzamy w identyczny sposób klasy <math>\displaystyle Ntime(t(n))</math> oraz
| |
| <math>\displaystyle Nspace(s(n))</math>.
| |
| | |
| Określamy następujące klasy złożoności (klasy języków):
| |
| | |
| <center><math>\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</math></center>
| |
| | |
| }}
| |
| | |
| Wprost z definicji otrzymujemy zależności '''P''' <math>\displaystyle \subset </math> '''NP''' oraz '''PSPACE''' <math>\displaystyle \subset </math> '''NPSPACE''' . W dalszej części wykładu udowodnimy kilka mniej oczywistych zależności.
| |
| | |
| {{przyklad|1.1||
| |
| Rozważmy język:
| |
| <center><math>\displaystyle
| |
| L=\left\{1^i 2^j 3^k\: k=i\cdot j,\: i,j\geqslant 1\right\}.
| |
| </math></center>
| |
| | |
| Język <math>\displaystyle L\in </math> '''P''' . Deterministyczna maszyna Turinga
| |
| <math>\displaystyle MT_3</math> akceptująca taki język może wyglądać następująco (zaczynamy
| |
| od konfiguracji <math>\displaystyle \sharp s_0 w \sharp</math>):
| |
| # Jeśli symbol pod głowicą, to <math>\displaystyle 1</math> zamień go na <math>\displaystyle\sharp</math>. Inaczej odrzuć.
| |
| # Przejdź od lewego ogranicznika do prawego, sprawdzając, czy po <math>\displaystyle 1</math> występuje <math>\displaystyle 1</math> lub <math>\displaystyle 2</math>, po <math>\displaystyle 2</math> tylko <math>\displaystyle 2</math> lub <math>\displaystyle 3</math>, a po <math>\displaystyle 3</math> kolejny symbol <math>\displaystyle 3</math> lub ogranicznik. Jeśli ta zależność nie jest spełniona, odrzuć. Gdy osiągniesz ogranicznik wykonaj następny krok.
| |
| # Gdy przed ogranicznikiem nie znajduje się symbol <math>\displaystyle 3</math>, odrzuć. W przeciwnym razie zamień symbol <math>\displaystyle 3</math> na <math>\displaystyle \sharp</math>, a następnie poruszaj się w lewo, aż dotrzesz do symbolu innego niż <math>\displaystyle 3</math> i <math>\displaystyle \diamondsuit</math>.
| |
| # Jeśli symbol do którego dotarłeś to <math>\displaystyle 2</math>, zamień go na <math>\displaystyle \diamondsuit</math>. Sprawdź symbol po lewej. Jeśli to <math>\displaystyle 2</math>, poruszaj się w prawo aż do ogranicznika. Następnie przejdź do kroku 3.
| |
| # Jeśli dotarłeś do symbolu <math>\displaystyle 1</math>, poruszaj się w lewo aż do ogranicznika. Zamień symbol <math>\displaystyle 1</math> przy ograniczniku na <math>\displaystyle \sharp</math>, a następnie idź w prawo, zamieniając wszystkie symbole <math>\displaystyle \diamondsuit</math> na <math>\displaystyle 2</math>. Gdy dojdziesz do ogranicznika, przejdź do kroku <math>\displaystyle 3</math>.
| |
| # Jeśli dotarłeś do ogranicznika, oznacza to, że skasowano już wszystkie symbole <math>\displaystyle 1</math>. Przejdź w prawo aż do ogranicznika. Jeśli natrafisz na symbol <math>\displaystyle 3</math>, odrzuć. W przeciwnym przypadku, akceptuj.
| |
| | |
| Nietrudno zaobserwować, że maszyna <math>\displaystyle MT_3</math> przechodzi przez taśmę w prawo i w lewo tyle
| |
| razy, ile symboli <math>\displaystyle 3</math> zawiera taśma oraz wykonuje jeden dodatkowy
| |
| przebieg na starcie. Zatem słowa z <math>\displaystyle L</math> są akceptowane w
| |
| czasie ograniczonym wielomianowo.
| |
| }}
| |
| | |
| {{kotwica|prz.1.2|}}{{przyklad|1.2||
| |
| | |
| Rozważmy teraz język
| |
| <center><math>\displaystyle
| |
| L=\left\{3^k\: : \: k=i\cdot j </math> dla pewnych <math>\displaystyle i,j> 1\rbrace.
| |
| </math></center>
| |
| | |
| Najprostszą metodą uzasadnienia, że <math>\displaystyle L\in </math> '''NP''' jest
| |
| konstrukcja tak zwanej wyroczni. Polega ona na następującej
| |
| dwuetapowej procedurze:
| |
| # Skonstruuj niedeterministyczną maszynę Turinga (wyrocznia) generującą pewne słowo (certyfikat).
| |
| # Zweryfikuj w sposób deterministyczny spełnienie założeń przez certyfikat.
| |
| | |
| W naszym przykładzie Etap 1 wygląda następująco:
| |
| # Użyj dwóch taśm. Na pierwszej z nich znajduje się <math>\displaystyle 3^k</math>.
| |
| # Idź po pierwszej taśmie, wykorzystując niedeterministyczną funkcję przejść. Napotykając <math>\displaystyle 3</math>, możesz wypisać <math>\displaystyle 1</math> 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.
| |
| # Powróć do początku pierwszej taśmy. Wykonaj sekwencję jak w kroku <math>\displaystyle 2</math>, z tą różnicą, że teraz na drugiej taśmie wypisuj symbole <math>\displaystyle 2</math>.
| |
| # Jako ostatnią część tego etapu przekopiuj symbole <math>\displaystyle 3</math> z pierwszej taśmy na drugą (po symbolach <math>\displaystyle 1</math> i <math>\displaystyle 2</math>).
| |
| | |
| 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 <math>\displaystyle 1^i 2^j 3^k</math>, gdzie <math>\displaystyle i,j>1</math> oraz <math>\displaystyle k=i\cdot j</math>. Jeśli tak, to słowo wejściowe <math>\displaystyle 3^k</math> pochodziło z języka <math>\displaystyle L</math> 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 <math>\displaystyle L</math>, 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 <math>\displaystyle L</math> nie ma to znaczenia.
| |
| | |
| Zastanów się, czy da się wykazać, że także <math>\displaystyle L\in </math> '''P'''
| |
| (Ćwiczenie '''1.3''', do tego wykładu).
| |
| }}
| |
| | |
| {{definicja|1.3||
| |
| Funkcja <math>\displaystyle s(n)</math> jest '''konstruowalna pamięciowo''', jeśli istnieje maszyna Turinga <math>\displaystyle \mathcal{MT}=(\Sigma _{T},S,f,s_{0},S_{F})</math>, dla
| |
| której <math>\displaystyle d_1 \mapsto^* d_2</math>, gdzie <math>\displaystyle d_1=\sharp s_0 1^n \sharp</math>,
| |
| <math>\displaystyle d_2=\sharp s_1 1^{s(n)} w \sharp</math> dla <math>\displaystyle s_1\in S_F</math>, <math>\displaystyle w\in
| |
| (\Sigma_T\setminus \left\{1\right\})^*</math> oraz dodatkowo <math>\displaystyle d_2</math> jest
| |
| konfiguracją końcową.
| |
| }}
| |
| | |
| Inaczej mówiąc, funkcję <math>\displaystyle s(n)</math> nazywamy konstruowalną pamięciowo, jeśli istnieje maszyna Turinga <math>\displaystyle \mathcal{MT}</math>, otrzymując na wejściu
| |
| słowo <math>\displaystyle w</math> długości <math>\displaystyle |w|=n</math>, zaznacza na taśmie roboczej <math>\displaystyle s(n)</math> klatek i zatrzymuje się (akceptując słowo <math>\displaystyle w</math>).
| |
| | |
| {{przyklad|1.3||
| |
| Funkcja <math>\displaystyle s(n)=2n</math> jest konstruowalna pamięciowo. Maszyna <math>\displaystyle MT_4</math>,
| |
| która konstruuje <math>\displaystyle s(n)</math> działa według schematu:
| |
| # Przejdź do prawego markera. Jeśli napotkano symbol inny niż <math>\displaystyle 1</math>, to odrzuć.
| |
| # Idź w lewo aż do pierwszego symbolu <math>\displaystyle 1</math> lub markera <math>\displaystyle \sharp</math>
| |
| # Jeśli napotkałeś symbol <math>\displaystyle 1</math>, zamień go na <math>\displaystyle \clubsuit</math> i przejdź do prawego markera. Dopisz do słowa symbol <math>\displaystyle \clubsuit</math> (zwiększając tym samym długość słowa na taśmie o <math>\displaystyle 1</math>). Następnie powtórz cykl od <math>\displaystyle 2</math>.
| |
| # Jeśli napotkałeś marker, idź w prawo, zamieniając wszystkie wystąpienia <math>\displaystyle \clubsuit</math> na <math>\displaystyle 1</math>. Następnie wracaj do lewego markera i zatrzymaj się, akceptując.
| |
| | |
| }}
| |
| | |
| {{kotwica|tw.1.1|}}{{twierdzenie|1.1 liniowa kompresja pamięci||
| |
| | |
| Niech będzie dany język <math>\displaystyle L</math> oraz maszyna Turinga
| |
| <math>\displaystyle \mathcal{TM}</math> akceptująca <math>\displaystyle L</math> w pamięci <math>\displaystyle s(n)</math>. Dla dowolnego
| |
| <math>\displaystyle \varepsilon>0</math> istnieje maszyna Turinga <math>\displaystyle \mathcal{TM}'</math> akceptująca <math>\displaystyle L</math> w
| |
| pamięci <math>\displaystyle \max\left\{n,\varepsilon s(n)\right\}</math>.
| |
| }}
| |
| | |
| {{dowod|||
| |
| (''Szkic'')
| |
| Ustalamy liczbę naturalną <math>\displaystyle k</math>, dla której <math>\displaystyle \varepsilon k\geqslant 2</math>. Maszynę
| |
| <math>\displaystyle \mathcal{TM}'</math> definiujemy następująco:
| |
| # Przekoduj słowo wejściowe, łącząc po <math>\displaystyle r</math> kolejnych symboli w jeden blok stanowiący nowy symbol na taśmie.
| |
| # Symuluj maszynę <math>\displaystyle \mathcal{MT}</math> na skompresowanej taśmie. Położenie głowicy wewnątrz bloku zakoduj w stanach maszyny <math>\displaystyle \mathcal{MT}'</math>.
| |
| | |
| Zauważmy, że w kroku <math>\displaystyle 1</math>. maszyna <math>\displaystyle \mathcal{MT}'</math> wykorzystuje <math>\displaystyle n</math>
| |
| komórek pamięci do odczytania słowa wejściowego. Kompresja taśmy
| |
| zapewnia, że podczas symulowania maszyny <math>\displaystyle \mathcal{MT}</math> nie
| |
| wykorzystamy więcej niż <math>\displaystyle \lceil \frac{s(n)}{k}\rceil \leqslant \varepsilon s(n)</math>
| |
| komórek. Jednocześnie można założyć, że <math>\displaystyle \mathcal{MT}'</math> akceptuje
| |
| słowa wejściowe z języka <math>\displaystyle L</math> o długości mniejszej niż <math>\displaystyle k</math> bez
| |
| symulowania <math>\displaystyle \mathcal{MT}</math>.
| |
| }}
| |
| | |
| {{twierdzenie|1.2 Savitch||
| |
| | |
| Dla dowolnej funkcji <math>\displaystyle s(n)</math> konstruowalnej pamięciowo spełniającej
| |
| warunek <math>\displaystyle s(n)\geqslant \log_2 n</math> prawdziwa jest inkluzja
| |
| <math>\displaystyle Nspace(s(n))\subset DSpace(s^2(n))</math>.
| |
| }}
| |
| | |
| {{dowod|||
| |
| Niech <math>\displaystyle \mathcal{NMT}</math> będzie niedeterministyczną maszyną Turinga
| |
| akceptującą język <math>\displaystyle L=L(\mathcal{NMT})</math> w pamięci <math>\displaystyle s(n)</math>. Niech
| |
| <math>\displaystyle k(n)</math> oznacza liczbę konfiguracji potrzebną do zaakceptowania słowa
| |
| o długości <math>\displaystyle n</math>. Istnieje liczba <math>\displaystyle c>1</math>, dla której <math>\displaystyle k(n)\leqslant c^{s(n)}</math>, co z kolei oznacza, że każde słowo o długości <math>\displaystyle n</math> jest akceptowane w <math>\displaystyle c^{s(n)}</math> krokach czasowych.
| |
| }}
| |
| Rozważmy algorytm:
| |
| | |
| {{algorytm|||
| |
| 1 Wejście: słowo <math>\displaystyle w</math> długości <math>\displaystyle |w|=n</math>
| |
| 2 oblicz <math>\displaystyle s(n)</math>
| |
| 3 '''for''' każda konfiguracja akceptująca <math>\displaystyle d_A</math> dla której <math>\displaystyle |d_A|\leqslant s(n)</math>
| |
| 4 '''do if''' Test(<math>\displaystyle \sharp s_0 w \sharp</math>, <math>\displaystyle d_A</math>, <math>\displaystyle s(n) \log_2 c</math>) '''then''' akceptuj
| |
| }}
| |
| | |
| gdzie procedura Test ma następującą postać:
| |
| | |
| {{algorytm|'''Procedure''' Test(<math>\displaystyle d</math>,<math>\displaystyle d'</math>,<math>\displaystyle i</math>)||
| |
| 1 '''if''' <math>\displaystyle i=0</math> '''and''' [ (<math>\displaystyle d=d'</math>) '''or''' (<math>\displaystyle d\mapsto d'</math>)] '''then return true'''
| |
| 2 '''else for''' każda konfiguracja <math>\displaystyle d''</math> dla której <math>\displaystyle |d''|\leqslant s(n)</math>
| |
| 3 '''do if''' Test(<math>\displaystyle d</math>,<math>\displaystyle d''</math>,<math>\displaystyle i-1</math>) '''and''' Test <math>\displaystyle d''</math>,<math>\displaystyle d'</math>,<math>\displaystyle i-1</math>)
| |
| 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ć <math>\displaystyle s(n)</math>
| |
| komórek taśmy, aby móc konstruować konfiguracje o długości
| |
| ograniczonej przez <math>\displaystyle s(n)</math> i móc następnie wykonywać na nich
| |
| symulację maszyny <math>\displaystyle \mathcal{NMT}</math>.
| |
| | |
| Zauważmy, że ilość konfiguracji jest ograniczona przez <math>\displaystyle s(n)</math>, a
| |
| głębokość rekursji przez <math>\displaystyle \log c^{s(n)}</math>. Oznacza to, że jesteśmy w
| |
| stanie skonstruować maszynę Turinga, która wymaga <math>\displaystyle c' s^2(n)</math> pamięci, gdzie <math>\displaystyle c'</math> jest pewną stałą. Na mocy Twierdzenia [[#tw.1.1|1.1]] jesteśmy w stanie określić maszynę <math>\displaystyle \mathcal{MT}</math> działającą w pamięci <math>\displaystyle s^2(n)</math>.
| |
| | |
| {{wniosek|1.1||
| |
| <center> '''PSPACE''' <math>\displaystyle = </math> '''NPSPACE''' </center>
| |
| | |
| }}
| |
| | |
| {{lemat|1.1||
| |
| Jeśli <math>\displaystyle g(n)\geqslant n</math>, to <math>\displaystyle Dtime(g(n))\subset Dspace(g(n))</math> oraz
| |
| <math>\displaystyle Ntime(g(n))\subset Nspace(g(n))</math>.
| |
| }}
| |
| | |
| {{dowod|||
| |
| Niech będzie dana maszyna deterministyczna <math>\displaystyle \mathcal{MT}</math>
| |
| akceptująca dany język <math>\displaystyle L</math> w czasie <math>\displaystyle g(n)</math>. Do akceptacji słowa <math>\displaystyle w</math>
| |
| o długości <math>\displaystyle n</math> maszyna wykorzystuje co najwyżej <math>\displaystyle g(n)</math> kroków
| |
| czasowych, czyli odwiedza co najwyżej <math>\displaystyle g(n)+1</math> komórek taśmy.
| |
| | |
| Na podstawie Twierdzenia [[#tw.1.1|1.1]] istnieje maszyna Turinga
| |
| <math>\displaystyle \mathcal{MT}'</math> wykorzystująca
| |
| <center><math>\displaystyle
| |
| \max \left\{n, \frac{1}{2}(g(n)+1)\right\}\leqslant g(n)
| |
| </math></center>
| |
| | |
| komórek pamięci. Dla niedeterministycznych maszyn Turinga argumentacja
| |
| jest identyczna.
| |
| }}
| |
| | |
| {{wniosek|1.2||
| |
| <center> '''P''' <math>\displaystyle \subset </math> '''NP''' <math>\displaystyle \subset
| |
| </math> '''PSPACE''' <math>\displaystyle = </math> '''NPSPACE''' </center>
| |
| | |
| }}
| |
| | |
| {{uwaga|1.2||
| |
| Nie jest znany przykład wykazujący silną inkluzję '''P''' <math>\displaystyle \varsubsetneq </math> '''NP''' ani dowód wykluczający istnienie takiego przykładu. Powszechnie uznawana
| |
| hipoteza głosi:
| |
| <center> '''P''' <math>\displaystyle \neq </math> '''NP'''. </center>
| |
| | |
| 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 [[#prz.1.2|1.2]], nawet w
| |
| przypadku konkretnego języka <math>\displaystyle L\in </math> '''NP''', problem
| |
| uzasadnienia, że także <math>\displaystyle L\in </math> '''P''', jest nietrywialny,
| |
| gdyż wymaga zazwyczaj konstrukcji całkiem nowej maszyny Turinga niż
| |
| ta do weryfikacji <math>\displaystyle L\in </math> '''NP''' .
| |
| }}
| |
| | |
| ==Redukcja i problemy zupełne==
| |
| | |
| {{definicja|2.1 transformacja wielomianowa||
| |
| | |
| Niech <math>\displaystyle L_1,L_2</math> będą dowolnymi językami nad pewnym alfabetem
| |
| <math>\displaystyle \Sigma_I</math>. Mówimy, że <math>\displaystyle L_1</math> redukuje się do <math>\displaystyle L_2</math> w czasie
| |
| wielomianowym, co oznaczamy <math>\displaystyle L_1 \propto L_2</math>, gdy istnieje
| |
| deterministyczna maszyna Turinga <math>\displaystyle \mathcal{MT}=(\Sigma
| |
| _{T},S,f,s_{0},S_{F})</math> taka, że dla dowolnego <math>\displaystyle w\in \Sigma_I^*</math>
| |
| istnieje <math>\displaystyle w'\in \Sigma_I^*</math> i stan <math>\displaystyle s_1\in S_F</math> o własności
| |
| <center><math>\displaystyle
| |
| \sharp s_0 w \sharp \mapsto^* \sharp s_1 w' \sharp
| |
| </math></center>
| |
| | |
| oraz
| |
| <center><math>\displaystyle
| |
| w\in L_1 \quad \Longleftrightarrow \quad w' \in L_2.
| |
| </math></center>
| |
| | |
| }}
| |
| | |
| {{lemat|2.1||
| |
| Załóżmy, że <math>\displaystyle L_1 \propto L_2</math>. Wtedy zachodzą implikacje:
| |
| # <math>\displaystyle L_2 \in </math> '''P''' <math>\displaystyle \quad \Longrightarrow \quad L_1 \in </math> '''P''',
| |
| # <math>\displaystyle L_2 \in </math> '''NP''' <math>\displaystyle \quad \Longrightarrow \quad L_1 \in </math> '''NP''',
| |
| # <math>\displaystyle L_2 \in </math> '''PSPACE''' <math>\displaystyle \quad \Longrightarrow \quad L_1 \in </math> '''PSPACE'''.
| |
| | |
| }}
| |
| | |
| {{dowod|||
| |
| Dane słowo <math>\displaystyle w</math> transformujemy do <math>\displaystyle w'</math> w czasie wielomianowym, co gwarantuje założenie <math>\displaystyle L_1 \propto L_2</math>. Dzięki założeniu <math>\displaystyle L_2 \in </math> '''P''' możemy rozstrzygnąć, czy <math>\displaystyle w'\in L_2</math> (tzn. jeśli akceptujemy <math>\displaystyle w'</math>, to robimy to w czasie wielomianowym). Tym sposobem (korzystając z definicji transformacji wielomianowej) akceptujemy <math>\displaystyle w</math> w czasie wielomianowym, o ile tylko <math>\displaystyle w\in L_1</math>. Dowód dla pozostałych implikacji jest identyczny.
| |
| }}
| |
| | |
| {{definicja|2.2||
| |
| Niech <math>\displaystyle \mathcal{C}</math> oznacza pewną klasę języków. Język <math>\displaystyle L</math> nazywamy '''<math>\displaystyle \mathcal{C}</math>-trudnym''', jeśli spełniony jest warunek:
| |
| <center><math>\displaystyle
| |
| \forall\; L' \in \mathcal{C} \quad L'\propto L.
| |
| </math></center>
| |
| | |
| Jeżeli dodatkowo spełniony jest warunek <math>\displaystyle L\in \mathcal{C}</math>, to język <math>\displaystyle L</math> nazywamy '''<math>\displaystyle \mathcal{C}</math>-zupełnym'''.
| |
| }}
| |
| | |
| Intuicyjnie, fakt, że język jest <math>\displaystyle \mathcal{C}</math>-zupełny, oznacza, że jest on najbardziej skomplikowany (pod względem obliczeniowym) wśród języków z klasy <math>\displaystyle \mathcal{C}</math>, natomiast język <math>\displaystyle \mathcal{C}</math>-trudny jest bardziej skomplikowany niż każdy z klasy
| |
| <math>\displaystyle \mathcal{C}</math>, 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.).
| |
| }}
| |
| | |
| {{przyklad|2.1||
| |
| Rozważmy języki:
| |
| <center><math>\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\}.
| |
| </math></center>
| |
| | |
| Języki: <math>\displaystyle L_1</math> oraz <math>\displaystyle L_2</math> wyglądają na bardzo podobne, zatem wydaje się, że <math>\displaystyle L_1 \propto L_2</math> oraz <math>\displaystyle L_2 \propto L_1</math>. Uzasadnienie tego faktu jest prawie natychmiastowe.
| |
| }}
| |
| Konstruujemy deterministyczną maszynę Turinga która działa w
| |
| następujący sposób:
| |
| # {{kotwica|prz.1|}} Jeśli słowo wejściowe jest puste, to stop.
| |
| # Przejdź do prawego ogranicznika. Jeśli przy ograniczniku nie występuje symbol <math>\displaystyle 4</math>, to wykonaj krok [[#prz.1|1]].
| |
| # Jeśli w słowie wejściowym występuje symbol <math>\displaystyle 4</math>, to sprawdź, czy słowo przetwarzane jest postaci <math>\displaystyle \sharp w 4^s \sharp</math>, gdzie <math>\displaystyle s\geqslant 1</math> oraz <math>\displaystyle w\in (\Sigma_I\setminus \left\{4\right\})^*</math> oraz czy dodatkowo <math>\displaystyle s</math> jest liczbą parzystą. Jeśli nie, to wykonaj krok [[#prz.1|1]].
| |
| # Zamień słowo <math>\displaystyle 4^s</math> na słowo <math>\displaystyle 3^{\frac{s}{2}}\sharp^{\frac{s}{2}}</math> i wykonaj krok [[#prz.1|1]].
| |
| # Przejdź nad pierwszy symbol po lewym ograniczniku i zatrzymaj się.
| |
| | |
| W ten sposób zawsze przeprowadzamy konfigurację <math>\displaystyle \sharp s_0 w \sharp
| |
| </math> na konfigurację <math>\displaystyle \sharp s_1 w' \sharp</math>, przy czym <math>\displaystyle w'=1^i 2^j 3^k</math>
| |
| tylko, gdy <math>\displaystyle w=1^i 2^j 4^{2k}</math>. Zatem <math>\displaystyle w\in L_2</math> wtedy i tylko wtedy, gdy <math>\displaystyle w'\in L_1</math>. Wykazaliśmy, że <math>\displaystyle L_2 \propto L_1</math>.
| |
| | |
| Warunek <math>\displaystyle L_1 \propto L_2</math> otrzymujemy w sposób identyczny. Trzeba
| |
| tylko wypisać odpowiednią ilość symboli <math>\displaystyle 4</math> (a wiemy już, jak
| |
| konstruować liczbę <math>\displaystyle 2n</math>, mając dane <math>\displaystyle n</math>).
| |
