Złożoność obliczeniowa/Wykałd 3: Klasy złożoności obliczeniowej: Różnice pomiędzy wersjami

Wersja z 22:43, 26 lip 2006

{theorem}{Theorem}[section] {lemma}[theorem]{Lemma} {tw}[theorem]{Twierdzenie} {definition}[theorem]{Definicja} {example}[theorem]{Przykład} {EX}[theorem]{Ćwiczenie} {observation}[theorem]{Observation} {proof}{ {Dowód: }}{ $◻$ } {hint}{ {Wskazówka: }}{} {sol}{ {Rozwiązanie: }}{}

{}{0.5cm} {}{0.8cm} {}{ -0.4cm} {}{ -0.4cm} {}{1mm} 14.6pt

{} {} {}

{ Informacje}

Przedmiot & Złożoność obliczeniowa
Moduł & 3
Tytuł & Klasy złożoności obliczeniowej
Opracowanie & Przemysław Broniek
{ Syllabus} Klasy złożoności obliczeniowej

klasy złożoności czasowej i pamięciowej,

twierdzenia o liniowym przyspieszaniu i kompresji pamięci,

relacje między klasami, twierdzenie Savitcha i dopełnienia klas,

twierdzenia o hierarchii czasowej i pamięciowej.

Klasy złożoności czasowej i pamięciowej

W poprzednich modułach zostały wprowadzone maszyny Turinga oraz zdefiniowane pojęcie problemu obliczeniowego. Przypomnijmy, że problem obliczeniowy to dla nas język, czyli zbiór słów. Poznaliśmy także szczegółowo maszynę w wersji deterministycznej i niedeterministycznej oraz jej miarę złożoności czasowej i pamięciowej w każdej z wersji. W tym module zajmiemy się klasyfikacją języków przy pomocy maszyn. W naszych dalszych rozważaniach przyjmujemy model obliczeń w postaci maszyny Turinga o $k$ taśmach.

Klasa złożoności obliczeniowej to zbiór problemów (języków) spełniających określone kryterium. Najbardziej podstawowe kryteria, tzn. czas i pamięć potrzebne do klasyfikacji języka dają nam podstawowe klasy złożoności:

Definicja [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \textsc{TIME}(f(n))} oznaczamy zbiór języków $L$ takich, że są akceptowane przez deterministyczną maszynę Turinga $M$ o złożoności czasowej $f (n)$ .

Definicja [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \textsc{SPACE}(f(n))} oznaczamy zbiór języków $L$ takich, że są akceptowane przez deterministyczną maszynę Turinga $M$ o złożoności pamięciowej $f (n)$ .

Stosowne klasy można też zdefiniować dla niedeterministycznych maszyn:

Definicja [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \textsc{NTIME}(f(n))} oznaczamy zbiór języków $L$ takich, że są akceptowane przez niedeterministyczną maszynę Turinga $M$ o złożoności czasowej $f (n)$ .

Definicja [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \textsc{NSPACE}(f(n))} oznaczamy zbiór języków $L$ takich, że są akceptowane przez niedeterministyczną maszynę Turinga $M$ o złożoności pamięciowej $f (n)$ .

Twierdzenia o liniowym przyspieszaniu i kompresji pamięci

Pierwsze dwa twierdzenia możemy nazwać "teoretycznymi podstawami" notacji $O$ . Pokażemy bowiem, że w obu powyższych definicjach klas funkcja $f (n)$ może być rozpatrywana z dokładnością do stałej, ze względu na specyfikę samego modelu obliczeń. Zostały one udowodnione w latach 60 przez pionierów badań nad klasami złożoności, laureatów nagrody Turinga z roku 1993, Jurisa Hartmanisa i Richarda Stearnsa.

Twierdzenie [Uzupelnij]

(twierdzenie o liniowym przyspieszaniu) Jeśli język

L

jest rozpoznawany przez maszynę

M

o złożoności czasowej

f (n)

to może

być rozpoznany przez maszynę $M^{'}$ o złożoności czasowej $f^{'} (n) = ϵ f (n) + (1 + ϵ) n$ , gdzie $ϵ > 0$ .

Dowód [Uzupelnij]

{{{3}}}

Twierdzenie nie ma zastosowania dla subliniowych funkcji złożoności, jednak maszyny, które nie czytają całego wejścia wydają się mało interesujące. W przypadku liniowej funkcji złożoności oznacza to, że stała może być dowolnie bliska 1.

Analogicznie twierdzenie zachodzi dla złożoności pamięciowej:

(twierdzenie o liniowej kompresji pamięci) Jeśli język $L$ jest rozpoznawany przez maszynę $M$ o złożoności pamięciowej $f (n)$ to może być rozpoznany przez maszynę $M^{'}$ o złożoności pamięciowej $f^{'} (n) = ϵ f (n)$ , gdzie $ϵ > 0$ .

Skorzystaj z dowodu twierdzenia o liniowym przyspieszaniu.

Dowód przebiega dokładnie tak samo jeśli chodzi o ideę. Wystarczy tylko dokonać obliczenia zużycia pamięci. Każda komórka nowej maszyny $M^{'}$ pamięta $c$ symboli maszyny $M$ , więc koszt pamięciowy to $f^{'} (n) = ⌈ f (n) / c ⌉ < ϵ f (n)$ , jeśli $c = ⌈ 1 / ϵ ⌉$ , dla odpowiednio dużych $n$ (ponownie dla małych $n$ można stosownie rozbudować maszynę).

Na koniec ciekawostka dotycząca przyspieszania maszyn. Mając dany język $L$ poszukujemy najszybszego algorytmu, który go akceptuje. Okazuje się, że jest język, dla którego nie istnieje algorytm asymptotycznie najszybszy! Autorem tego przeczącego intuicji twierdzenia jest Manuel Blum, laureat nagrody Turinga z roku 1995.

Twierdzenie [Uzupelnij]

(twierdzenie Bluma o przyspieszaniu) Istnieje język $L$ , taki, że jeśli jest akceptowany przez maszynę Turinga o złożoności czasowej $f (n)$ , to jest również akceptowany, przez maszynę Turinga o złożoności czasowej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{log}(f(n))} .

Relacje między klasami, twierdzenie Savitcha

Teraz jesteśmy gotowi do wprowadzenia podstawowych klas złożoności, w których funkcje są wyłącznie asymptotyczne:

Klasa P = Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{TIME}(n^k) = \bigcup_{j>0} \textnormal{TIME}(n^j)} , to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wielomianowym,

Klasa NP = Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NTIME}(n^k) = \bigcup_{j>0} \textnormal{NTIME}(n^j)} , to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wielomianowym,

Klasa EXP = TIME( $2^{n^{k}}$ ), to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wykładniczym,

Klasa NEXP = NTIME( $2^{n^{k}}$ ), to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wykładniczym.

dla klas pamięciowych:

Klasa L = SPACE({log} $n$ ), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci logarytmicznej,

Klasa NL = NSPACE({log} $n$ ), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,

Klasa PSPACE = SPACE( $n^{k}$ ), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wielomianowej,

Klasa NPSPACE = NSPACE( $n^{k}$ ), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wielomianowej,

Klasa EXPSPACE = SPACE( $2^{n^{k}}$ ), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wykładniczej,

Klasa NEXPSPACE = NSPACE( $2^{n^{k}}$ ), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wykładniczej.

Teraz zajmiemy się relacjami pomiędzy poszczególnymi klasami złożoności. Najbardziej podstawowe zależności, łączące czas, pamięć i niedeterminizm to:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{TIME}(f(n))\subseteq\textnormal{NTIME}(f(n))} , gdyż z definicji, każda maszyna deterministyczna jest maszyną niedeterministyczną,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{SPACE}(f(n))\subseteq\textnormal{NSPACE}(f(n))} , jak wyżej,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{TIME}(f(n))\subseteq\textnormal{SPACE}(f(n))} , gdyż maszyna nie może zapisać więcej komórek niż wynosi jej czas działania,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NTIME}(f(n))\subseteq\textnormal{NSPACE}(f(n))} , jak wyżej,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NTIME}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})} , na podstawie twierdzenia z modułu pierwszego o symulacji

maszyny niedeterministycznej przez maszynę deterministyczną.

Aby powiedzieć więcej o relacjach pomiędzy klasami musimy narzucić pewne rozsądne ograniczenie na funkcję złożoności $f (n)$ . Powiemy, że $f (n)$ jest konstruowalna pamięciowo, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle f(n)\geqslant \textnormal{log}n} oraz istnieje deterministyczna maszyna Turinga, która mając na wejściu $n$ zapisane unarnie potrafi zużyć dokładnie $f (n)$ komórek pamięci i zatrzymać się.

Zawężamy się w ten sposób do funkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle f(n)\geqslant \textnormal{log}n} , lecz mniejszych złożoności nie będziemy tutaj rozważać (mimo, iż można). Warto dodać, że jeśli maszyna działa w pamięci Parser nie mógł rozpoznać (błąd składni): {\displaystyle o(\textnormal{log log}n)} to działa w pamięci stałej.

Okazuje się, że większość interesujących funkcji spełnia tą własność. Jest to także własność zamknięta ze względu na dodawanie, mnożenie i potęgowanie.

Pokaż, że funkcje Parser nie mógł rozpoznać (błąd składni): {\displaystyle \lceil \textnormal{log}n \rceil} , $n^{k}$ , $2^{n}$ są konstruowalne pamięciowo.

Zastosuj definicję i skonstruuj stosowne maszyny.

Dowód konstruowalności pamięciowej funkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \lceil \textnormal{log}n \rceil} opieramy na implementacji klasycznego licznika binarnego. Długość zapisu liczby binarnej $n$ to właśnie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \lceil \textnormal{log}n \rceil} . Dla funkcji wielomianowej wykonujemy serię prostych działań arytmetycznych polegających na mnożeniu i dodawaniu liczb naturalnych zapisanych binarnie. W przypadku funkcji wykładniczej wystarczy zaprogramować maszynę, aby $n$ razy dokonała podwojenia liczby zużytych komórek.

Poniżej przedstawiamy twierdzenie, które zachodzi, jeśli nie narzucimy dodatkowego warunku na funkcję złożoności. Wprowadzając go, chcemy uniknąć podobnych sytuacji:

Twierdzenie [Uzupelnij]

(twierdzenie o luce) Istnieje funkcja rekurencyjna $f (n)$ taka, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{TIME}(f(n))=\textnormal{TIME}(2^{f(n)})} .

Dowód [Uzupelnij]

Przedstawimy bardzo specyficzną definicję funkcji $f (n)$ , dla której każda maszyna na słowie o długości $n$ działa w czasie co najwyżej $f (n)$ lub działa przynajmniej $2^{f (n)} + 1$ kroków lub pętli się. W ten sposób pokażemy stosowną równość klas. Dowód opiera się na bardzo użytecznej i często stosowanej technice przekątniowej.

Będziemy rozważać wszystkie możliwe maszyny w pewnej ustalonej kolejności $M_{1}, M_{2}, \dots$ wynikającej np. z leksykograficznego porządku na ich kodach zdefiniowanych w module pierwszym. Ponieważ każda maszyna może być opisana skończonym słowem, więc wygenerowanie takiego ciągu wszystkich maszyn jest wykonalne.

Zdefiniujmy relację binarną $P (i, k)$ w ten sposób, by była spełniona, gdy każda maszyna od $1$ do $i$ działając na dowolnym słowie o długości $i$ działa w czasie co najwyżej $k$ lub działa przynajmniej $2^{k} + 1$ kroków lub pętli się. Tą relację jesteśmy w stanie obliczyć poprzez stosowną symulację maszyn $M_{1}, \dots, M_{i}$ na wszystkich słowach długości $i$ przez co najwyżej $2^{k} + 1$ kroków (oczywiście jest to dosyć czasochłonne), tym samym ewentualne pętlenie się maszyn nie stanowi przeszkody.

Teraz jesteśmy gotowi do zdefiniowania $f (n)$ . Ustalmy $n$ . Zauważmy, że $P (n, k)$ musi być prawdziwa dla pewnego $k$ . Dzieje się tak dlatego, gdyż wraz ze wzrostem $k$ zmieniamy zabroniony obszar czasu działania maszyn od $1$ do $n$ . Liczba słów które testujemy jest jednak ograniczona -- są to wszystkie słowa o długości dokładnie $n$ dla tych maszyn. Aby $P (n, k)$ nie było prawdą to czas działania maszyny na słowie musi trafić do obszaru zabronionego, co wobec ustalonej liczby słów i zwiększania $k$ spowoduje, że $P (n, k)$ w końcu będzie prawdą. Definiujemy wartość $f (n)$ jako najmniejsze takie $k$ .

Weźmy dowolny język Parser nie mógł rozpoznać (błąd składni): {\displaystyle L\in\textnormal{TIME}(2^{f(n)})} . Jest on akceptowany przez maszynę, którą oznaczmy $M_{j}$ (w naszym porządku ustalonym w pierwszej części). Maszyna ma złożoność $2^{f (n)}$ . Weźmy dowolne słowo o długości $l ⩾ j$ . Wiemy, że $P (l, f (l))$ jest spełnione, a tym samym maszyna $M_{j}$ działa w czasie co najwyżej $f (l)$ (bo więcej niż $2^{f (l)}$ nie może z definicji klasy). Zatem Parser nie mógł rozpoznać (błąd składni): {\displaystyle L\in\textnormal{TIME}(f(n))} .

Pominęliśmy działanie na słowach krótszych niż $j$ , jednakże jest to stała liczba słów, które łatwo zaakceptować w czasie rzędu ich długości po prostu wbudowując ich przynależność do $L$ w maszynę.

W literaturze rozważa się wiele wersji "normujących" dopuszczalne funkcji złożoności, np. właściwie funkcje złożoności lub funkcje uczciwe. Różnice między nimi są dosyć techniczne. Przyjmijmy zatem, że funkcje złożoności $f (n)$ są konstruowalne pamięciowo.

Przeanalizujmy teraz możliwe konfiguracje maszyny Turinga $M$ , które tworzą tzw. graf przejść maszyny:

W jak wielu konfiguracjach może znaleźć się maszyna Turinga o złożoności pamięciowej $f (n)$ (konstruowalnej pamięciowo) przeprowadzając obliczenie na słowie o długości $n$ ?

Policz liczbę stanów maszyny, położeń głowic i zawartości taśm.

Liczba możliwych konfiguracji to oczywiście iloczyn:

liczby stanów $| Q |$ ,

położeń głowic na wszystkich taśmach, jest rzędu $f (n)^{k}$ jednak nie mniej niż $n$ (dokładny wynik zależy od przyjętych wyróżnień taśmy wejściowej i wyjściowej),

zawartości taśm, czyli $| Γ |^{k f (n)}$ .

Razem możemy to ograniczyć przez $c^{f (n)}$ , dla pewnego $c$ zależnego tylko od maszyny oraz korzystając z założenia, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle f(n)\geqslant \textnormal{log}n} , gdyż jest konstruowalna pamięciowo.

Teraz jesteśmy gotowi do wypowiedzenia kolejnych interesujących relacji pomiędzy wprowadzonymi klasami:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{SPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})} , ze względu na fakt, iż liczba możliwych konfiguracji maszyny o złożoności pamięciowej $f (n)$ ,

co pokazaliśmy przed chwilą wynosi $c^{f (n)}$ , zatem maszyna, która się nie pętli może zostać zasymulowana przez maszynę działającą co najwyżej tak długo. W przeciwnym wypadku wpadła by w nieskończoną pętlę.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NTIME}(f(n))\subseteq\textnormal{SPACE}(f(n))} , gdyż maszyna deterministyczna może zasymulować działanie maszyny niedeterministycznej.

Wystarczy wygenerować po kolei każdy z ciągów $f (n)$ niedeterministycznych wyborów (tu korzystamy z pamięciowej konstruowalności), których musi ona dokonać w trakcie obliczeń. Następnie dokonujemy już deterministycznej symulacji obliczeń przez $f (n)$ kroków. Wszystkie te operacje można dokonać w dostępnej pamięci $f (n)$ , gdyż każdy z ciągów niedeterministycznych wyborów możemy symulować w tej samej pamięci,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})} , ponownie opierając się na symulacji maszyny.

Jak poprzednio liczba wszystkich konfiguracji wynosi $c^{f (n)}$ , jednak tym razem przejścia pomiędzy poszczególnymi konfiguracjami tworzą graf. Wystarczy jednak obliczyć, czy istnieje ścieżka od konfiguracji początkowej do konfiguracji końcowej, co może być obliczone w czasie wielomianowym ze względu na rozmiar grafu, a zatem w czasie asymptotycznym $c^{f (n)}$ .

Dzięki powyższym relacjom możemy wypisać kilka podstawowych zależności pomiędzy wprowadzonymi klasami:

Uzasadnij każdą z poniższych relacji:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{L}\subseteq\textnormal{NL}\subseteq\textnormal{P}\subseteq\textnormal{NP}\subseteq\textnormal{PSPACE}}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{PSPACE}\subseteq\textnormal{NPSPACE}\subseteq\textnormal{EXP}\subseteq\textnormal{NEXP}\subseteq\textnormal{EXPSPACE}\subseteq\textnormal{NEXPSPACE}}

Skorzystaj z poznanych już własności klas oraz własności funkcji logarytmicznej, wielomianowej i wykładniczej.

Wszystkie zawierania pochodzą z wypisanych wcześniej ogólnych zależności. Nietrywialne, to:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NL}\subseteq\textnormal{P}} , korzystamy z faktu, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})} , w tym wypadku

mamy bowiem Parser nie mógł rozpoznać (błąd składni): {\displaystyle c^{\textnormal{log}n}=n^k} ,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NPSPACE}\subseteq\textnormal{EXP}} , również korzystamy z faktu, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})} , w tym wypadku

mamy bowiem $c^{n^{k}} = 2^{n^{k^{'}}}$ .

Przyjrzyjmy się bliżej pierwszej serii relacji z poprzedniego ćwiczenia i zobrazujmy ją na rysunku:

{1cm}

[width=10cm]{ZO-3-3-rys.jpg}
Relacje pomiędzy podstawowymi klasami

{1cm}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{L}\subseteq\textnormal{NL}\subseteq\textnormal{P}\subseteq\textnormal{NP}\subseteq\textnormal{PSPACE}} W następnej części z twierdzenia o hierarchii pamięciowej dowiemy się, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle L\varsubsetneq \textnormal{PSPACE}} . Tym samym wiemy, że pierwszy i ostatni element są różne. Jedną z najbardziej fascynujących rzeczy w teorii złożoności jest fakt, że przynajmniej jedno z czterech powyższych zawierań musi być ścisłe, jednakże o żadnym z nich tego nie wiadomo! Najsłynniejszy fragment to oczywiście pytanie o zawieranie pomiędzy P i NP.

Ostatnią i najciekawszą relacją pomiędzy klasami jest ta odkryta przez Savitcha, mówiąca o niewielkiej przewadze niedeterministycznej złożoności pamięciowej. Przypomnijmy, że do tej pory wiemy poprzez połączenie dwóch wymienionych własności, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NSPACE}(f(n))\subseteq\textnormal{SPACE}(c^{f(n)})} . Okazuje się, że zachodzi twierdzenie dużo silniejsze:

Twierdzenie [Uzupelnij]

(twierdzenie Savitcha) Jeśli $f (n)$ jest konstruowalna pamięciowo, to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NSPACE}(f(n))\subseteq\textnormal{SPACE}(f^2(n))} .

Dowód [Uzupelnij]

{{{3}}}

Na podstawie twierdzenia Savitcha wiemy, że niektóre z poznanych klas są sobie równe:

PSPACE = NPSPACE,

EXPSPACE = NEXPSPACE.

czyli, że niedeterminizm w złożoności pamięciowej dla większych funkcji nic nie daje. Dla klas złożoności czasowej takiej wiedzy nie posiadamy!

Złożoność obliczeniowa/Wykałd 3: Klasy złożoności obliczeniowej: Różnice pomiędzy wersjami

Wersja z 22:43, 26 lip 2006

Klasy złożoności czasowej i pamięciowej

Twierdzenia o liniowym przyspieszaniu i kompresji pamięci

Relacje między klasami, twierdzenie Savitcha

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-[section]
+{theorem}{Theorem}[section]
+{lemma}[theorem]{Lemma}
+{tw}[theorem]{Twierdzenie}
+{definition}[theorem]{Definicja}
+{example}[theorem]{Przykład}
+{EX}[theorem]{Ćwiczenie}
+{observation}[theorem]{Observation}
+{proof}{ {Dowód: }}{ <math>\square</math>}
+{hint}{ {Wskazówka: }}{}
+{sol}{ {Rozwiązanie: }}{}
-{Lemma}
+{}{0.5cm} {}{0.8cm} {}{ -0.4cm} {}{ -0.4cm} {}{1mm}  14.6pt
-{Twierdzenie}
+{} {} {}
-{Definicja}
+{ '''Informacje'''}
-{Przykład}
+{|l|l|}
-{Ćwiczenie}
+Przedmiot & '''Złożoność obliczeniowa''' <br>
-{Observation}
+Moduł &  '''3''' <br>
-{\hfill <math>\square</math>}
+Tytuł &  '''Klasy złożoności obliczeniowej''' <br>
-{}
-{}
-\fancyhf{} \lhead{\leftmark} \rhead{\thepage}
-\addtolength{\textheight}{0.5cm} \addtolength{\textwidth}{0.8cm} \addtolength{\oddsidemargin}{ -0.4cm} \addtolength{\evensidemargin}{ -0.4cm} \setlength{\unitlength}{1mm} \headheight 14.6pt
-{\Huge \bfInformacje}
-\begin_center
-\begin_tabular{|l|l|}
-\hline
-Przedmiot & '''Złożoność obliczeniowa''' <br>
-\hline
-Moduł &  '''3''' <br>
-\hline
-Tytuł &  '''Klasy złożoności obliczeniowej''' <br>
-\hline
 Opracowanie &  '''Przemysław Broniek''' <br>
-\hline
-\end_tabular
-\end_center
+{ Syllabus}
-{\Huge \bfSyllabus}
 Klasy złożoności obliczeniowej
@@ Linia 52: / Linia 37: @@
 * twierdzenia o hierarchii czasowej i pamięciowej.
-\newpage
 ==Klasy złożoności czasowej i pamięciowej==
@@ Linia 112: / Linia 95: @@
 wytwarzania komputerów. Na rysunku przedstawiono schematycznie zamianę 8 komórek pamięci na jedną większą nowej maszyny:
-\vspace{1cm}
+{1cm}
-\begin_center
-\includegraphics[width=10cm]{ZO-3-1-rys.jpg}<br>
+[width=10cm]{ZO-3-1-rys.jpg}<br>
 Liniowe przyspieszanie
-\end_center
-\vspace{1cm}
+{1cm}
 Nasza nowa maszyna o powiększonym alfabecie rozpoczyna działanie od skompresowania słowa wejściowego na drugiej taśmie i zamiany ról taśmy drugiej i wejściowej. Następnie
@@ Linia 136: / Linia 119: @@
 W drugim etapie dokonujemy symulacji. Najpierw odczytujemy "obszar trzech" komórek na każdej taśmie co zajmuje 4 kroki <math>M'</math>:
-\vspace{1cm}
+{1cm}
-\begin_center
-\includegraphics[width=10cm]{ZO-3-2-rys.jpg}<br>
+[width=10cm]{ZO-3-2-rys.jpg}<br>
 Obszar trzech
-\end_center
-\vspace{1cm}
+{1cm}
 Zapamiętujemy odczyt
@@ Linia 162: / Linia 145: @@
 Analogicznie twierdzenie zachodzi dla złożoności pamięciowej:
-{{theorem|| (twierdzenie o liniowej kompresji pamięci) Jeśli język <math>L</math> jest rozpoznawany przez maszynę <math>M</math> o złożoności pamięciowej <math>f(n)</math> to może
+(twierdzenie o liniowej kompresji pamięci) Jeśli język <math>L</math> jest rozpoznawany przez maszynę <math>M</math> o złożoności pamięciowej <math>f(n)</math> to może
 być rozpoznany przez maszynę <math>M'</math> o złożoności pamięciowej <math>f'(n)=\epsilon f(n)</math>, gdzie <math>\epsilon>0</math>.
-}}
-{{\noindent ''Wskazówka: ''||
 Skorzystaj z dowodu twierdzenia o liniowym przyspieszaniu.
-}}
-{{\noindent ''Rozwiązanie: ''||
 Dowód przebiega dokładnie tak samo jeśli chodzi o ideę. Wystarczy tylko dokonać obliczenia zużycia pamięci. Każda komórka nowej maszyny <math>M'</math>
 pamięta <math>c</math> symboli maszyny <math>M</math>, więc koszt pamięciowy to <math>f'(n)=\lceil f(n)/c \rceil<\epsilon f(n)</math>, jeśli <math>c=\lceil 1/\epsilon \rceil</math>,
 dla odpowiednio dużych <math>n</math> (ponownie dla małych <math>n</math> można stosownie rozbudować maszynę).
-}}
 Na koniec ciekawostka dotycząca przyspieszania maszyn.
@@ Linia 201: / Linia 179: @@
 dla klas pamięciowych:
-* Klasa L = SPACE(\textnormal{log}<math>n</math>), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci logarytmicznej,
+* Klasa L = SPACE({log}<math>n</math>), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci logarytmicznej,
-* Klasa NL = NSPACE(\textnormal{log}<math>n</math>), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,
+* Klasa NL = NSPACE({log}<math>n</math>), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,
 * Klasa PSPACE = SPACE(<math>n^k</math>), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wielomianowej,
@@ Linia 235: / Linia 213: @@
 Okazuje się, że większość interesujących funkcji spełnia tą własność. Jest to także własność zamknięta ze względu na dodawanie, mnożenie i potęgowanie.
-{{theorem||
 Pokaż, że funkcje <math>\lceil \textnormal{log}n \rceil</math>, <math>n^k</math>, <math>2^n</math> są konstruowalne pamięciowo.
-}}
-{{\noindent ''Wskazówka: ''||
 Zastosuj definicję i skonstruuj stosowne maszyny.
-}}
-{{\noindent ''Rozwiązanie: ''||
 Dowód konstruowalności pamięciowej funkcji
 <math>\lceil \textnormal{log}n \rceil</math> opieramy na implementacji klasycznego licznika binarnego. Długość zapisu liczby binarnej <math>n</math> to właśnie <math>\lceil \textnormal{log}n \rceil</math>.
 Dla funkcji wielomianowej wykonujemy serię prostych działań arytmetycznych polegających na mnożeniu i dodawaniu liczb naturalnych zapisanych binarnie.
 W przypadku funkcji wykładniczej wystarczy zaprogramować maszynę, aby <math>n</math> razy dokonała podwojenia liczby zużytych komórek.
-}}
 Poniżej przedstawiamy twierdzenie, które zachodzi, jeśli nie narzucimy dodatkowego warunku na funkcję złożoności. Wprowadzając go, chcemy uniknąć podobnych
@@ Linia 291: / Linia 263: @@
 Przeanalizujmy teraz możliwe konfiguracje maszyny Turinga <math>M</math>, które tworzą tzw. graf przejść maszyny:
-{{theorem||
 W jak wielu konfiguracjach może znaleźć się maszyna Turinga o złożoności pamięciowej
 <math>f(n)</math> (konstruowalnej pamięciowo) przeprowadzając obliczenie na słowie o długości <math>n</math>?
-}}
-{{\noindent ''Wskazówka: ''||
 Policz liczbę stanów maszyny, położeń głowic i zawartości taśm.
-}}
-{{\noindent ''Rozwiązanie: ''||
 Liczba możliwych konfiguracji to oczywiście iloczyn:
@@ Linia 311: / Linia 278: @@
 Razem możemy to ograniczyć przez <math>c^{f(n)}</math>, dla pewnego <math>c</math> zależnego tylko od maszyny oraz korzystając z założenia, że
 <math>f(n)\geqslant \textnormal{log}n</math>, gdyż jest konstruowalna pamięciowo.
-}}
 Teraz jesteśmy gotowi do wypowiedzenia kolejnych interesujących relacji pomiędzy wprowadzonymi klasami:
@@ Linia 331: / Linia 297: @@
 Dzięki powyższym relacjom możemy wypisać kilka podstawowych zależności pomiędzy wprowadzonymi klasami:
-{{theorem|| Uzasadnij każdą z poniższych relacji:<br>
+Uzasadnij każdą z poniższych relacji:<br>
 * <math>\textnormal{L}\subseteq\textnormal{NL}\subseteq\textnormal{P}\subseteq\textnormal{NP}\subseteq\textnormal{PSPACE}</math>
@@ Linia 337: / Linia 303: @@
 * <math>\textnormal{PSPACE}\subseteq\textnormal{NPSPACE}\subseteq\textnormal{EXP}\subseteq\textnormal{NEXP}\subseteq\textnormal{EXPSPACE}\subseteq\textnormal{NEXPSPACE}</math>
-}}
-{{\noindent ''Wskazówka: ''||
 Skorzystaj z poznanych już własności klas oraz własności funkcji logarytmicznej, wielomianowej i wykładniczej.
-}}
-{{\noindent ''Rozwiązanie: ''||
 Wszystkie zawierania pochodzą z wypisanych wcześniej ogólnych zależności. Nietrywialne, to:
@@ Linia 352: / Linia 313: @@
 mamy bowiem <math>c^{n^k}=2^{n^{k'}}</math>.
-}}
+Przyjrzyjmy się bliżej pierwszej serii relacji z poprzedniego ćwiczenia i zobrazujmy ją na rysunku:
-Przyjrzyjmy się bliżej pierwszej serii relacji z poprzedniego ćwiczenia i zobrazujmy ją na rysunku:
+{1cm}
-\vspace{1cm}
+[width=10cm]{ZO-3-3-rys.jpg}<br>
-\begin_center
-\includegraphics[width=10cm]{ZO-3-3-rys.jpg}<br>
 Relacje pomiędzy podstawowymi klasami
-\end_center
-\vspace{1cm}
+{1cm}
 <math>\textnormal{L}\subseteq\textnormal{NL}\subseteq\textnormal{P}\subseteq\textnormal{NP}\subseteq\textnormal{PSPACE}</math>
@@ Linia 394: / Linia 353: @@
 oznaczmy przez <math>t</math>:
-\vspace{1cm}
+{1cm}
-\begin_center
-\includegraphics[width=10cm]{ZO-3-4-rys.jpg}<br>
+[width=10cm]{ZO-3-4-rys.jpg}<br>
 Wierzchołek pośredni
-\end_center
-\vspace{1cm}
+{1cm}
 Potem wywołujemy rekurencyjnie <math>\textnormal{PATH}(x,t,i/2)</math> oraz <math>\textnormal{PATH}(t,y,i/2)</math>. Jeśli obie ścieżki istnieją to zwracamy 1,
@@ Linia 417: / Linia 376: @@
 czyli, że niedeterminizm w złożoności pamięciowej dla większych funkcji nic nie daje.
 Dla klas złożoności czasowej takiej wiedzy nie posiadamy!
-===Dopełnienia klas===
-W tym rozdziale przyjrzymy się dopełnieniom języków i klas. Jeśli <math>L</math> jest językiem to przez <math>\overline{L}=\sum^*\setminus L</math>
-oznaczamy jego dopełnienie. W przypadku problemów decyzyjnych ''dopełnienie'' (ang. COMPLEMENT) to problem decyzyjny,
-w którym odpowiedzi są odwrócone.
-Jeśli rozważymy SAT, w którym pytamy czy formuła może zostać spełniona,
-to jego dopełnienie to SAT COMPLEMENT. Jest to problem bardzo blisko spokrewniony z TAUTOLOGY, w którym pytamy czy każde wartościowanie
-formuły <math>\phi</math> ją spełnia. SAT COMPLEMENT to pytanie, czy formuła nie ma wartościowań spełniających, co
-jest równoważne temu, że <math>\neg \phi</math> jest formułą zawsze spełnioną, czyli jest tautologią logiczną.
-COMPLEMENT nie jest ściśle dopełnieniem języka, gdyż <math>\overline{SAT}</math> zawiera także wszystkie słowa, które nie są poprawnymi
-opisami formuł. Te słowa nie stanowią jednak problemu w rozpoznawaniu.
-Zdefiniujemy teraz pojęcie dopełnienia klasy złożoności. Przypomnijmy, że klasy złożoności składają się z języków.
-Jeśli <math>C</math> jest dowolną klasą złożoności to przez <math>\textnormal{co}C</math>
-oznaczamy jej ''dopełnienie'', które jest złożone z dopełnień języków z klasy <math>C</math>.
-Zauważmy od razu, że jeśli <math>C</math> jest klasą deterministyczną, to <math>\textnormal{co}C=C</math> ze względu na fakt, iż
-maszyna deterministyczna, która akceptuje język <math>L\in C</math> po zamianie rolami stanu akceptującego i odrzucającego
-stanie się maszyną akceptującą język <math>\overline{L}</math>.
-W module dotyczącym pamięci logarytmicznej dowiemy się, że klasy niedeterministycznej złożoności pamięciowej
-również zamknięte są na dopełnienia, natomiast w przypadku klas niedeterministycznych złożoności
-czasowej ''nie wiemy'' jakie są relacje pomiędzy nimi i jest to problem otwarty.
-===Twierdzenia o hierarchii czasowej i pamięciowej===
-W tej części poznamy dwa ważne twierdzenia, które wprowadzają pojęcia hierarchii czasowej i pamięciowej, tzn. pokażemy, że
-większe złożoności rzeczywiście istotnie pozwalają akceptować więcej języków.
-{{twierdzenie|[Uzupelnij]||
-(twierdzenie o hierarchii pamięciowej)
-Jeśli <math>f(n)</math> jest konstruowalna pamięciowo oraz <math>g(n) \in o(f(n))</math> (czyli rośnie asymptotycznie wolniej) to
-<math>\textnormal{SPACE}(g(n)) \subsetneq  \textnormal{SPACE}(f(n))</math>.
-}}
-{{dowod|[Uzupelnij]||
-Pokażemy, że istnieje język <math>L\in\textnormal{SPACE}(f(n))</math> taki, że <math>L\notin\textnormal{SPACE}(g(n))</math>.
-Aby zapewnić pierwszy warunek, skonstruujemy maszynę <math>M</math> dla <math>L</math>, która ma złożoność pamięciową <math>f(n)</math>.
-Drugi warunek zapewnimy pokazując, że żadna z maszyn o złożoności pamięciowej <math>g(n)</math> nie akceptuje <math>L</math>.
-Maszyna <math>M</math> działa następująco. Gdy na wejściu dostanie słowo o długości <math>n</math> to w pierwszym etapie
-oznakowuje <math>f(n)</math> komórek pamięci na każdej z taśm. Będziemy bowiem symulować inne maszyny i chcemy się upewnić, że
-nie zużywają one więcej niż <math>f(n)</math> pamięci. Możemy to zrobić dzięki konstruowalności pamięciowej <math>f(n)</math>.
-Teraz następuje część przekątniowa:
-\vspace{1cm}
-\begin_center
-\includegraphics[width=10cm]{ZO-3-5-rys.jpg}<br>
-Maszyna przekątniowa
-\end_center
-\vspace{1cm}
-W drugim etapie maszyna <math>M</math> interpretuje słowo <math>x</math> z wejścia jako kod maszyny <math>M'</math>. Maszyna <math>M</math> odrzuca słowa, które nie są poprawnymi kodami.
-Gdy kod jest poprawny, to rozpoczyna się symulacja <math>M'</math> na tym samym słowie <math>x</math>. Jeśli symulacja
-przekroczy oznakowaną pamięć <math>f(n)</math> to maszyna <math>M</math> również odrzuca słowo <math>x</math>. Jeśli maszyna <math>M'</math> zaakceptuje <math>x</math>
-to maszyna <math>M</math> odrzuca <math>x</math> i jeśli <math>M'</math> odrzuca <math>x</math> to <math>M</math> je akceptuje.
-Maszyna <math>M</math> ma złożoność pamięciową <math>f(n)</math>, więc <math>L=L(M)\in\textnormal{SPACE}(f(n))</math>.
-Zastanówmy się, czy język <math>L</math> należy do klasy <math>\textnormal{SPACE}(g(n))</math>. Wtedy jest akceptowany przez
-maszynę <math>M'</math> o złożoności <math>g(n)</math>. Zastanówmy się co dzieje się, gdy <math>M'</math> dostanie na wejściu swój kod <math>\textnormal{<}M'\textnormal{>}</math>.
-Ponieważ <math>M'</math> akceptuje język w czasie <math>g(n)</math>, więc i na słowie <math>x</math> działa w takim czasie. Załóżmy, że
-odrzuca <math>x</math>. Wtedy maszyna <math>M</math> zaakceptuje <math>x</math>, gdyż symulacja którą ona przeprowadza, tzn. działanie <math>M'</math> na <math>x</math>
-może zostać przeprowadzona, jako że <math>g(n)</math> jest asymptotycznie mniejsze niż <math>f(n)</math> (pomijamy szczegóły techniczne, które pojawią się dla małych <math>n</math>).
-Analogicznie, gdy <math>M'</math> akceptuje <math>x</math> to <math>M</math> je odrzuca, czyli <math>M'</math> nie może akceptować <math>L</math>, gdyż myli się na <math>x=\textnormal{<}M'\textnormal{>}</math>.
-Otrzymujemy sprzeczność, stąd <math>L \notin \textnormal{SPACE}(g(n))</math>.
-}}
-A teraz pora na analogiczne twierdzenie o hierarchii czasowej.
-Potrzebne jest nam do niego dodatkowe ograniczenie na funkcję złożoności. Powiemy, że <math>f(n)</math>
-jest ''konstruowalna czasowo'', gdy <math>f(n)\geqslant n\textnormal{log}n</math> oraz istnieje deterministyczna maszyna Turinga, która mając na wejściu <math>n</math> zapisane unarnie potrafi
-działać przez dokładnie <math>f(n)</math> kroków i zatrzymać się. Również w tym wypadku większość znanych funkcji jest konstruowalna.
-{{twierdzenie|[Uzupelnij]||
-(twierdzenie o hierarchii czasowej)
-Jeśli <math>f(n)</math> jest konstruowalna czasowo oraz <math>g(n) \in o(f(n)/\textnormal{log}f(n))</math> to
-<math>\textnormal{TIME}(g(n)) \subsetneq  \textnormal{TIME}(f(n))</math>.
-}}
-Dowód jest przedmiotem ćwiczenia końcowego. Teraz możemy wyciągnąć kilka ważnych wniosków o ''silnym'' zawieraniu się klas złożoności:
-* <math>\textnormal{SPACE}(n^{\epsilon_1})\subsetneq\textnormal{SPACE}(n^{\epsilon_2})</math>, gdy <math>0\leqslant\epsilon_1 < \epsilon_2</math>,
-z własności funkcji wielomianowej,
-* <math>\textnormal{TIME}(n^{\epsilon_1})\subsetneq\textnormal{TIME}(n^{\epsilon_2})</math>, gdy <math>1\leqslant\epsilon_1 < \epsilon_2</math>, jak wyżej,
-* <math>\textnormal{L}\subsetneq\textnormal{PSPACE}</math>, gdyż logarytm rośnie wolniej niż funkcja wielomianowa,
-* <math>\textnormal{P}\subsetneq\textnormal{EXP}</math>,  korzystamy z własności, że każdy wielomian rośnie wolniej
-niż funkcja subwykładnicza <math>n^{\textnormal{log}n}</math> a ta z kolei rośnie wolniej, niż każda funkcja wykładnicza.
-* <math>\textnormal{PSPACE}\subsetneq\textnormal{EXPSPACE}</math>, jak wyżej.
-Widzimy zatem, że klasa P, pojmowana jako zbiór praktycznie rozwiązywalnych problemów również podlega hierarchii. Istnieją w niej języki
-które są akceptowane w czasie <math>n^{10000}</math> natomiast w <math>n^{9999}</math> już nie. To sprawia, że należy patrzeć na praktyczność klasy P
-z pewną ostrożnością.
-==Ćwiczenia dodatkowe==
-{{theorem||
-Udowodnij twierdzenie o hierarchii czasowej:<br>
-Jeśli <math>f(n)</math> jest konstruowalna czasowo oraz <math>g(n) \in o(f(n)/\textnormal{log}f(n))</math> to
-<math>\textnormal{TIME}(g(n)) \subsetneq  \textnormal{TIME}(f(n))</math>.
-}}
-{{\noindent ''Wskazówka: ''||
-Przeprowadź rozumowanie podobne jak w dowodzie twierdzenia o hierarchii pamięciowej.
-}}
-{{\noindent ''Rozwiązanie: ''||
-Jak w dowodzie twierdzenia o hierarchii pamięciowej skonstruujemy maszynę <math>M</math>, której język <math>L=L(M)</math>
-należy do <math>\textnormal{TIME}(f(n))</math>, ale nie należy do <math>\textnormal{TIME}(g(n))</math>.
-Konstruujemy <math>M</math> tak, że bierze <math>x</math> z wejścia i traktuje jako kod maszyny. Następnie
-symuluje jej działanie nie jak poprzednio w pamięci <math>f(n)</math> lecz w czasie <math>f(n)</math>.
-Aby jednak dokonać takiej symulacji maszyna <math>M</math> musi zliczać liczbę wykonanych kroków
-symulacji. Symulacja każdego kroku zajmuje teraz <math>\textnormal{log}(f(n))</math> potrzebnych do zaimplementowania
-licznika. Stąd można zasymulować każdą maszynę o złożoności asymptotycznie mniejszej niż <math>f(n)\textnormal{log}f(n)</math>
-a tym samym wykazać przy pomocy przekątniowej metody, że język <math>M</math> jest różny od języka każdej z tych maszyn.
-}}
-{{theorem||
-Udowodnij następujące fakty:
-* <math>\textnormal{NTIME}(n)\subsetneq \textnormal{PSPACE}</math>
-* <math>\textnormal{TIME}(2^n) = \textnormal{TIME}(2^{n+1})</math>
-* <math>\textnormal{TIME}(2^n)\subsetneq \textnormal{TIME}(2^{2n})</math>
-}}
-{{\noindent ''Wskazówka: ''||
-Użyj poznanych twierdzeń o przyspieszaniu i hierarchii.
-}}
-{{\noindent ''Rozwiązanie: ''||<br>
-Ad. 1:<br>
-Wiemy, że <math>\textnormal{NTIME}(n) \subseteq \textnormal{SPACE}(n)</math>.
-Następnie na podstawie twierdzenia o hierarchii pamięciowej <math>\textnormal{SPACE}(n) \subsetneq \textnormal{PSPACE}</math>, co kończy dowód.<br>
-Ad. 2:<br>
-Oczywiście <math>\textnormal{TIME}(2^n) \subseteq \textnormal{TIME}(2^{n+1})</math>.
-Weźmy teraz dowolny język <math>L</math> należący do klasy <math>\textnormal{TIME}(2^{n+1})</math>. Istnieje zatem maszyna działająca w czasie <math>2^{n+1}</math>.
-Z twierdzenia o przyspieszaniu wiemy, że istnieje inna maszyna <math>M'</math>
-akceptująca ten sam język <math>L</math>, ale działająca w czasie <math>2^{n+1}/4</math>, gdy zastosujemy <math>\epsilon = 1/4</math> (czynnik liniowy
-obok funkcji wykładniczej jest nieistotny). Lecz <math>2^{n+1}/4=2^n/2</math>, a zatem <math>L</math> należy do <math>\textnormal{TIME}(2^n)</math> co dowodzi tezy.<br>
-Ad. 3:<br>
-Zastosujemy twierdzenie o hierarchii czasowej dla funkcji <math>f(n)=2^{2n}</math> oraz <math>g(n)=2^n</math>.
-Musimy tylko wykazać, że funkcje spełniają założenia twierdzenia. Mamy jednak <math>f(n)/\textnormal{log}(f(n))=2^{2n}/2n=(2^n/2n)2^n</math>
-zatem dominuje asymptotycznie <math>2^n</math> co kończy dowód.
-}}
-==Testy końcowe==