|
|
| Linia 1: |
Linia 1: |
| Sformułujemy definicje podstawowych klas
| | \newtheorem{thm}{Twierdzenie} |
| złożoności w języku maszyn Turinga oraz metodę ich porównywania.
| | \newtheorem{obs}[thm]{Obserwacja} |
| Przeanalizujemy związki między rodziną języków określonych przez maszyny Turinga a
| | \newtheorem{con}[thm]{Wniosek} |
| rodziną języków typu '''(0)''' z hierarchii Chomsky'ego. Podamy dalsze własności
| | \newtheorem{exrr}{Zadanie} |
| 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==
| | \parindent 0mm |
|
| |
|
| Jednym z podstawowych celów wprowadzania maszyn Turinga jest dążenie
| | '''#1''' |
| do formalnej definicji złożoności obliczeniowej. Na podstawie
| | \parindent 10mm }{\hfill{ <math>\displaystyle \square </math> } |
| 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 <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
| | {article} |
| \mapsto d_m</math>, gdzie <math>\displaystyle d_1=\sharp s_0 w \sharp</math>, <math>\displaystyle d_m</math> jest
| | \input{../makraT} |
| 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>
| | \newpage |
| (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||
| | \parindent 0mm |
| W niektórych podejściach wykorzystuje się, do definicji złożoności
| | \beginLarge |
| 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|| | | {| border=1 |
| Oznaczmy przez <math>\displaystyle Dtime(t(n))</math> oraz <math>\displaystyle Dspace(s(n))</math> rodzinę języków
| | |+ <span style="font-variant:small-caps">Uzupelnij tytul</span> |
| akceptowanych w czasie <math>\displaystyle t(n)</math> i odpowiednio pamięci <math>\displaystyle s(n)</math> przez
| | |- |
| deterministyczną maszynę Turinga. Dla maszyn niedeterministycznych
| | | '''Indukcja''' |
| 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&
| | \endLarge |
| \textbd{NP} \displaystyle =\bigcup_{k=0}^\infty Ntime(n^k),
| | \parindent 10mm |
| \\
| |
| \textbd{PSPACE} \displaystyle =\bigcup_{k=0}^\infty Dspace(n^k), &&
| |
| \textbd{NSPACE} \displaystyle =\bigcup_{k=0}^\infty Nspace(n^k).
| |
| \endaligned</math></center> | |
|
| |
|
| }} | | ; Zaznacz zdania prawdziwe dotyczące podłogi i sufitu: |
| | : |
| | |
| | :; <math>\displaystyle n\geq 2^{\left\lceil \log_2 n \right\rceil} </math> , |
| | :: |
| | |
| | :; <math>\displaystyle n\leq 2^{\left\lceil \log_2 n \right\rceil} </math> , |
| | :: |
| | |
| | :; <math>\displaystyle \left\lceil \log_2 \left\lceil n/2 \right\rceil \right\rceil=\left\lceil \log_2 \left( n/2 \right) \right\rceil </math> , |
| | :: |
| | |
| | :; <math>\displaystyle \left\lfloor \log_2 \left\lceil n/2 \right\rceil \right\rfloor=\left\lfloor \log_2 \left( n/2 \right) \right\rfloor </math> . |
| | :: |
| | |
| | ; Dowolny niepusty podzbiór <math>\displaystyle S\subseteq \mathbb{N} </math> zbioru liczb naturalnych |
| | : |
| | |
| | :; ma w sobie liczbę największą |
| | :: |
| | |
| | :; ma w sobie liczbę najmniejszą |
| | :: |
| | |
| | :; ma w sobie liczbę największą oraz liczbę najmniejszą |
| | :: |
| | |
| | :; ma w sobie liczbę najmniejszą ale nigdy nie ma największej |
| | :: |
| | |
| | ; Zbiór <math>\displaystyle S\subseteq\mathbb{N} </math> jest taki, że jeśli <math>\displaystyle s\in S </math> to <math>\displaystyle s+1\in S </math> . |
| | Jeśli <math>\displaystyle 9\in S </math> , to: |
| | : |
|
| |
|
| 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.
| | :; <math>\displaystyle S=\mathbb{N} </math> |
| | :: |
|
| |
|
| {{przyklad|1.1||
| | :; <math>\displaystyle S=\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace </math> |
| 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 S\subseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace </math> |
| <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
| | :; <math>\displaystyle S\supseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace </math> |
| 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.
| | ; Zbiór <math>\displaystyle S\subseteq\mathbb{N} </math> jest taki, że jeśli <math>\displaystyle a,b\in S </math> , |
| }}
| | to <math>\displaystyle a+b\in S </math> oraz <math>\displaystyle a+b+1\not\in S </math> . |
| | Jeśli <math>\displaystyle 0,2 \in S </math> , to: |
| | : |
|
| |
|
| {{kotwica|prz.1.2|}}{{przyklad|1.2|| | | :; <math>\displaystyle S=\mathbb{N} </math> |
| | :: |
|
| |
|
| Rozważmy teraz język
| | :; zbiór <math>\displaystyle S </math> zawiera wszystkie liczby naturalne, które są parzyste |
| <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
| | :; zbiór <math>\displaystyle S </math> jest zawarty w zbiorze liczb naturalnych, które są parzyste |
| 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:
| | :; zbiór <math>\displaystyle S </math> jest zbiorem wszystkich liczb naturalnych, które są parzyste |
| # 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>.
| | ; Ostatnią cyfrą liczby <math>\displaystyle 3^{3^n} </math> jest: |
| # 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
| | :; zawsze <math>\displaystyle 3 </math> |
| 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ę
| | :; zawsze <math>\displaystyle 3 </math> lub <math>\displaystyle 7 </math> |
| 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.
| | :; zawsze <math>\displaystyle 7 </math> |
| | :: |
|
| |
|
| Zastanów się, czy da się wykazać, że także <math>\displaystyle L\in </math> '''P'''
| | :; jakakolwiek z cyfr <math>\displaystyle 0,1,2,3,4,5,6,7,8,9 </math> |
| (Ćwiczenie '''1.3''', do tego wykładu).
| | :: |
| }}
| | |
| | ; Jeśli <math>\displaystyle Z \subseteq \mathbb{N} </math> jest jakimś zbiorem liczb naturalnych, |
| | który wraz z każdym początkowym fragmentem zbioru <math>\displaystyle \mathbb{N} </math> |
| | postaci <math>\displaystyle \left\lbrace 0,\ldots,k-1 \right\rbrace </math> zawiera również kolejną liczbę <math>\displaystyle k </math> , to wtedy |
| | : |
|
| |
|
| {{definicja|1.3||
| | :; zbiór <math>\displaystyle Z </math> zawiera wszystkie liczby naturalne poza skończonym podzbiorem |
| 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
| | :; zbiór <math>\displaystyle Z </math> zawiera wszystkie liczby naturalne |
| 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||
| | :; zbiór <math>\displaystyle Z </math> zawiera nieskończenie wiele liczb naturalnych |
| 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.
| |
|
| |
|
| }}
| | :; zbiór <math>\displaystyle Z </math> jest pusty |
| | :: |
| | |
| | ; Grupa uczniów stojących przed klasą skłóciła się do tego stopnia, |
| | że nikt z nikim się nie lubił. |
| | Jeden z nich, aby naprawić relacje, wymyślił, |
| | że jeżeli wszyscy znajdujący się wewnątrz klasy będą pogodzeni, |
| | to nie powinno być problemu, |
| | aby któryś stojący na zewnątrz klasy wszedł do środka i pogodził się ze wszystkimi, |
| | będącymi w klasie. |
| | Drugi z nich zauważył jednak, |
| | że nic z tego nie wyjdzie, bo w środku nikogo nie ma. |
| | Czy klasa jest w stanie się pogodzić? |
| | : |
|
| |
|
| {{kotwica|tw.1.1|}}{{twierdzenie|1.1 liniowa kompresja pamięci||
| | :; klasa na pewno się nie pogodzi |
| | :: |
|
| |
|
| Niech będzie dany język <math>\displaystyle L</math> oraz maszyna Turinga
| | :; klasa się pogodzi, jeżeli każdy pójdzie za radą pierwszego ucznia |
| <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|||
| | :; jeżeli w klasie byłaby już jedna osoba, to reszta klasy miałaby szansę się pogodzić |
| (''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>
| | :; jeżeli w klasie byłyby już co najmniej dwie osoby, |
| komórek pamięci do odczytania słowa wejściowego. Kompresja taśmy
| | przy czym osoby w klasie byłyby ze sobą pogodzone, |
| zapewnia, że podczas symulowania maszyny <math>\displaystyle \mathcal{MT}</math> nie
| | to reszta klasy miałaby szansę się pogodzić |
| 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
| | ; Jeśli <math>\displaystyle S\subseteq\mathbb{N} </math> , to: |
| symulowania <math>\displaystyle \mathcal{MT}</math>.
| | : |
| }}
| | |
| | | :; zbiór <math>\displaystyle S </math> ma element największy |
| {{twierdzenie|1.2 Savitch||
| | :: |
| | | |
| Dla dowolnej funkcji <math>\displaystyle s(n)</math> konstruowalnej pamięciowo spełniającej
| | :; zbiór <math>\displaystyle S </math> ma element najmniejszy |
| warunek <math>\displaystyle s(n)\geqslant \log_2 n</math> prawdziwa jest inkluzja
| | :: |
| <math>\displaystyle Nspace(s(n))\subset DSpace(s^2(n))</math>.
| | |
| }}
| | :; zbiór <math>\displaystyle S </math> ma element największy, o ile <math>\displaystyle S </math> jest niepusty |
| | | :: |
| {{dowod|||
| | |
| Niech <math>\displaystyle \mathcal{NMT}</math> będzie niedeterministyczną maszyną Turinga
| | :; zbiór <math>\displaystyle S </math> ma element najmniejszy, o ile <math>\displaystyle S </math> jest niepusty |
| 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>).
| |
