|
|
| Linia 1: |
Linia 1: |
| [section]
| |
|
| |
|
| {Lemma}
| |
|
| |
| {Twierdzenie}
| |
|
| |
| {Definicja}
| |
|
| |
| {Przykład}
| |
|
| |
| {Ćwiczenie}
| |
|
| |
| {Observation}
| |
|
| |
| \addtolength{\textheight}{0.5cm} \addtolength{\textwidth}{0.8cm} \addtolength{\oddsidemargin}{ -0.4cm} \addtolength{\evensidemargin}{ -0.4cm} \setlength{\unitlength}{1mm} \headheight 14.6pt
| |
|
| |
| \fancyhf{} \lhead{\leftmark} \rhead{\thepage}
| |
|
| |
| \newenvironment{proof}{\noindent ''Dowód: ''}{\hfill <math>\square</math>}
| |
| \newenvironment{hint}{\noindent ''Wskazówka: ''}{}
| |
| \newenvironment{sol}{\noindent ''Rozwiązanie: ''}{}
| |
|
| |
| {\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
| |
|
| |
| {\Huge \bfSyllabus}
| |
|
| |
| 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.
| |
|
| |
| \newpage
| |
|
| |
| ==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
| |
| <math>k</math> 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 <math>\textsc{TIME}(f(n))</math> oznaczamy zbiór języków <math>L</math> takich, że są akceptowane przez deterministyczną maszynę Turinga <math>M</math> o złożoności
| |
| czasowej <math>f(n)</math>.
| |
| }}
| |
|
| |
| {{definicja|[Uzupelnij]||
| |
| Poprzez <math>\textsc{SPACE}(f(n))</math> oznaczamy zbiór języków <math>L</math> takich, że są akceptowane przez deterministyczną maszynę Turinga <math>M</math> o złożoności
| |
| pamięciowej <math>f(n)</math>.
| |
| }}
| |
|
| |
| Stosowne klasy można też zdefiniować dla niedeterministycznych maszyn:
| |
|
| |
| {{definicja|[Uzupelnij]||
| |
| Poprzez <math>\textsc{NTIME}(f(n))</math> oznaczamy zbiór języków <math>L</math> takich,
| |
| że są akceptowane przez niedeterministyczną maszynę Turinga <math>M</math> o
| |
| złożoności czasowej <math>f(n)</math>.
| |
| }}
| |
|
| |
| {{definicja|[Uzupelnij]||
| |
| Poprzez <math>\textsc{NSPACE}(f(n))</math> oznaczamy zbiór języków <math>L</math> takich, że są akceptowane przez niedeterministyczną maszynę Turinga <math>M</math> o złożoności
| |
| pamięciowej <math>f(n)</math>.
| |
| }}
| |
|
| |
| ==Twierdzenia o liniowym przyspieszaniu i kompresji pamięci==
| |
|
| |
| Pierwsze dwa twierdzenia możemy nazwać "teoretycznymi podstawami"
| |
| notacji <math>O</math>. Pokażemy bowiem, że w obu powyższych definicjach klas
| |
| funkcja <math>f(n)</math> 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 <math>L</math> jest rozpoznawany przez maszynę <math>M</math> o złożoności czasowej <math>f(n)</math> to może
| |
| być rozpoznany przez maszynę <math>M'</math> o złożoności czasowej <math>f'(n)=\epsilon f(n) + (1+\epsilon) n</math>, gdzie <math>\epsilon>0</math>.
| |
| }}
| |
|
| |
| {{dowod|[Uzupelnij]||
| |
| Idea dowodu jest oparta na powiększeniu alfabetu maszyny, a tym samym wielkości "słowa" maszyny oraz liczby jej stanów.
| |
| Odpowiada to w praktyce podniesieniu technologii
| |
| wytwarzania komputerów. Na rysunku przedstawiono schematycznie zamianę 8 komórek pamięci na jedną większą nowej maszyny:
| |
|
| |
| \vspace{1cm}
| |
| \begin_center
| |
| \includegraphics[width=10cm]{ZO-3-1-rys.jpg}<br>
| |
| Liniowe przyspieszanie
| |
| \end_center
| |
| \vspace{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
| |
| głowica powraca na początek słowa i rozpoczyna obliczenia.
| |
|
| |
| W każdym kroku obliczeń <math>M'</math> odczytuje bieżącą komórkę oraz dwie sąsiednie (na wszystkich taśmach), a następnie symuluje zachowanie <math>M</math> w obszarze tych trzech komórek dzięki
| |
| zwiększonej stosownie liczbie stanów.
| |
| Jako efekt następuje modyfikacja bieżącej komórki i komórek sąsiednich oraz stosowne przesunięcie głowicy.
| |
|
| |
| Policzmy, czy taka symulacja rzeczywiście może być opłacalna. Załóżmy, że każda z komórek <math>M'</math> odpowiada <math>c</math> komórkom maszyny <math>M</math>, gdzie <math>c</math> - stopień
| |
| kompresji, który ostatecznie ustalimy na końcu (będzie on oczywiście zależał od <math>\epsilon</math> i <math>M</math>). Alfabet nowej maszyny <math>\Gamma'</math> to alfabet starej maszyny <math>\Gamma</math>
| |
| powiększony o symbole postaci <math>\Gamma^c</math>, które zapewniają nam zapis <math>c</math> symboli <math>M</math> w jednym symbolu <math>M'</math>.
| |
|
| |
| W pierwszym etapie <math>M'</math> musi dokonać kompresji, czyli odczytać <math>c</math> symboli i zapisać 1 symbol skompresowany. Do tego celu wystarczy jej istnienie
| |
| około <math>|\Gamma^c|</math> dodatkowych stanów. W ostatnim skompresowanym symbolu dokładamy symbole puste dla wyrównania.
| |
| Czas działania tego etapu to około <math>n+\lceil n/c \rceil</math> (odczyt związany z kompresją + powrót).
| |
|
| |
| 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}
| |
| \begin_center
| |
| \includegraphics[width=10cm]{ZO-3-2-rys.jpg}<br>
| |
| Obszar trzech
| |
| \end_center
| |
| \vspace{1cm}
| |
|
| |
| Zapamiętujemy odczyt
| |
| dzięki
| |
| stosownemu powiększeniu liczby stanów <math>M'</math>, które wykonujemy podobnie jak przy kompresji. Tym razem nowy zbiór stanów powiększamy o około <math>\Gamma^{3c}</math>
| |
| (trzeba jeszcze pamiętać o zapamiętaniu pozycji każdej głowic wewnątrz obszarów, te szczegóły techniczne pomijamy).
| |
| W tym momencie mamy pełną wiedzę kiedy maszyna <math>M</math> opuści "obszar trzech" i jak zostanie on zmodyfikowany.
| |
| Oczywiście jeśli w tym czasie maszyna <math>M</math> kończy działanie, to tak robi również <math>M'</math>. W przeciwnym wypadku "obszar trzech" jest modyfikowany kolejnymi 4 ruchami
| |
| <math>M'</math> i cykl rozpoczyna się od nowa. Wiemy jednak, że aby <math>M</math> opuściła obszar trzech komórek <math>M'</math> to musi wykonać przynajmniej <math>c</math> ruchów.
| |
| Przyspieszyliśmy zatem działanie przynajmniej o czynnik <math>c/8</math>.
| |
|
| |
| Podsumowując koszt czasowy to <math>f'(n)=n+\lceil n/c \rceil+\lceil 8f(n)/c \rceil<(1+\epsilon)n + \epsilon f(n)</math>, jeśli <math>c=\lceil 8/\epsilon \rceil</math>,
| |
| dla odpowiednio dużych <math>n</math> (dla małych
| |
| <math>n</math> można stosownie rozbudować maszynę).
| |
| }}
| |
|
| |
| 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:
| |
|
| |
| {{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
| |
| 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>.
| |
| }}
| |
|
| |
| \begin_hint
| |
| Skorzystaj z dowodu twierdzenia o liniowym przyspieszaniu.
| |
| \end_hint
| |
|
| |
| \begin_sol
| |
| 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ę).
| |
| \end_sol
| |
|
| |
| Na koniec ciekawostka dotycząca przyspieszania maszyn.
| |
| Mając dany język <math>L</math> 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 <math>L</math>, taki, że jeśli jest akceptowany przez maszynę Turinga o złożoności czasowej <math>f(n)</math>, to jest
| |
| również akceptowany, przez maszynę Turinga o złożoności czasowej <math>\textnormal{log}(f(n))</math>.
| |
| }}
| |
|
| |
| ==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 = <math>\textnormal{TIME}(n^k) = \bigcup_{j>0} \textnormal{TIME}(n^j)</math>, to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wielomianowym,
| |
|
| |
| * Klasa NP = <math>\textnormal{NTIME}(n^k) = \bigcup_{j>0} \textnormal{NTIME}(n^j)</math>, to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wielomianowym,
| |
|
| |
| * Klasa EXP = TIME(<math>2^{n^k}</math>), to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wykładniczym,
| |
|
| |
| * Klasa NEXP = NTIME(<math>2^{n^k}</math>), to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wykładniczym.
| |
|
| |
| 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 NL = NSPACE(\textnormal{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,
| |
|
| |
| * Klasa NPSPACE = NSPACE(<math>n^k</math>), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wielomianowej,
| |
|
| |
| * Klasa EXPSPACE = SPACE(<math>2^{n^k}</math>), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wykładniczej,
| |
|
| |
| * Klasa NEXPSPACE = NSPACE(<math>2^{n^k}</math>), 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:
| |
|
| |
| * <math>\textnormal{TIME}(f(n))\subseteq\textnormal{NTIME}(f(n))</math>, gdyż z definicji, każda maszyna deterministyczna jest maszyną niedeterministyczną,
| |
|
| |
| * <math>\textnormal{SPACE}(f(n))\subseteq\textnormal{NSPACE}(f(n))</math>, jak wyżej,
| |
|
| |
| * <math>\textnormal{TIME}(f(n))\subseteq\textnormal{SPACE}(f(n))</math>, gdyż maszyna nie może zapisać więcej komórek niż wynosi jej czas działania,
| |
|
| |
| * <math>\textnormal{NTIME}(f(n))\subseteq\textnormal{NSPACE}(f(n))</math>, jak wyżej,
| |
|
| |
| * <math>\textnormal{NTIME}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})</math>, 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 <math>f(n)</math>. Powiemy, że <math>f(n)</math>
| |
| jest ''konstruowalna pamięciowo'', gdy <math>f(n)\geqslant \textnormal{log}n</math> oraz istnieje deterministyczna maszyna Turinga, która mając na wejściu <math>n</math> zapisane unarnie potrafi
| |
| zużyć dokładnie <math>f(n)</math> komórek pamięci i zatrzymać się.
| |
|
| |
| Zawężamy się w ten sposób do funkcji <math>f(n)\geqslant \textnormal{log}n</math>, 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 <math>o(\textnormal{log log}n)</math> 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.
| |
|
| |
| {{theorem||
| |
| Pokaż, że funkcje <math>\lceil \textnormal{log}n \rceil</math>, <math>n^k</math>, <math>2^n</math> są konstruowalne pamięciowo.
| |
| }}
| |
|
| |
| \begin_hint
| |
| Zastosuj definicję i skonstruuj stosowne maszyny.
| |
| \end_hint
| |
|
| |
| \begin_sol
| |
| 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.
| |
| \end_sol
| |
|
| |
| 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 <math>f(n)</math> taka, że <math>\textnormal{TIME}(f(n))=\textnormal{TIME}(2^{f(n)})</math>.
| |
| }}
| |
|
| |
| {{dowod|[Uzupelnij]||
| |
| Przedstawimy bardzo specyficzną definicję funkcji <math>f(n)</math>, dla której każda maszyna na słowie o długości <math>n</math> działa w czasie co najwyżej <math>f(n)</math> lub
| |
| działa przynajmniej <math>2^{f(n)}+1</math> 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 <math>M_1, M_2, \ldots</math> 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ą <math>P(i,k)</math> w ten sposób, by była spełniona, gdy każda maszyna od <math>1</math> do <math>i</math> działając na dowolnym słowie o długości
| |
| <math>i</math> działa w czasie co najwyżej <math>k</math> lub działa przynajmniej <math>2^k+1</math> kroków lub pętli się. Tą relację jesteśmy w stanie obliczyć poprzez stosowną symulację maszyn <math>M_1, \ldots, M_i</math>
| |
| na wszystkich słowach długości <math>i</math> przez co najwyżej <math>2^k+1</math> 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 <math>f(n)</math>. Ustalmy <math>n</math>. Zauważmy, że <math>P(n,k)</math> musi być prawdziwa dla pewnego <math>k</math>. Dzieje się tak dlatego, gdyż wraz
| |
| ze wzrostem <math>k</math> zmieniamy zabroniony obszar czasu działania maszyn od <math>1</math> do <math>n</math>. Liczba słów które testujemy jest jednak ograniczona
| |
| -- są to wszystkie słowa o długości dokładnie <math>n</math> dla tych maszyn. Aby <math>P(n,k)</math> 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 <math>k</math> spowoduje, że <math>P(n,k)</math> w końcu będzie prawdą.
| |
| Definiujemy wartość <math>f(n)</math> jako najmniejsze takie <math>k</math>.
| |
|
| |
| Weźmy dowolny język <math>L\in\textnormal{TIME}(2^{f(n)})</math>. Jest on akceptowany przez maszynę, którą oznaczmy <math>M_j</math> (w naszym porządku ustalonym w pierwszej
| |
| części). Maszyna ma złożoność <math>2^{f(n)}</math>. Weźmy dowolne słowo o długości <math>l\geqslant j</math>. Wiemy, że <math>P(l,f(l))</math> jest spełnione, a tym
| |
| samym maszyna <math>M_j</math> działa w czasie co najwyżej <math>f(l)</math> (bo więcej niż <math>2^{f(l)}</math> nie może z definicji klasy). Zatem <math>L\in\textnormal{TIME}(f(n))</math>.
| |
|
| |
| Pominęliśmy działanie na słowach krótszych niż <math>j</math>, 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 <math>L</math> 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 <math>f(n)</math> są konstruowalne pamięciowo.
| |
|
| |
| 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>?
| |
| }}
| |
|
| |
| \begin_hint
| |
| Policz liczbę stanów maszyny, położeń głowic i zawartości taśm.
| |
| \end_hint
| |
|
| |
| \begin_sol
| |
| Liczba możliwych konfiguracji to oczywiście iloczyn:
| |
|
| |
| * liczby stanów <math>|Q|</math>,
| |
|
| |
| * położeń głowic na wszystkich taśmach, jest rzędu <math>f(n)^k</math> jednak nie mniej niż <math>n</math> (dokładny wynik zależy od przyjętych wyróżnień taśmy wejściowej i wyjściowej),
| |
|
| |
| * zawartości taśm, czyli <math>|\Gamma|^{k f(n)}</math>.
| |
|
| |
| 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.
| |
| \end_sol
| |
|
| |
| Teraz jesteśmy gotowi do wypowiedzenia kolejnych interesujących relacji pomiędzy wprowadzonymi klasami:
| |
|
| |
| * <math>\textnormal{SPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})</math>, ze względu na fakt, iż liczba możliwych konfiguracji maszyny o złożoności pamięciowej <math>f(n)</math>,
| |
| co pokazaliśmy przed chwilą wynosi <math>c^{f(n)}</math>, 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ę.
| |
|
| |
| * <math>\textnormal{NTIME}(f(n))\subseteq\textnormal{SPACE}(f(n))</math>, gdyż maszyna deterministyczna może zasymulować działanie maszyny niedeterministycznej.
| |
| Wystarczy wygenerować po kolei każdy z ciągów <math>f(n)</math> 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 <math>f(n)</math> kroków. Wszystkie te operacje można dokonać w dostępnej pamięci <math>f(n)</math>, gdyż
| |
| każdy z ciągów niedeterministycznych wyborów możemy symulować w tej samej pamięci,
| |
|
| |
| * <math>\textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})</math>, ponownie opierając się na symulacji maszyny.
| |
| Jak poprzednio liczba wszystkich konfiguracji wynosi <math>c^{f(n)}</math>, 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 <math>c^{f(n)}</math>.
| |
|
| |
| 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>
| |
|
| |
| * <math>\textnormal{L}\subseteq\textnormal{NL}\subseteq\textnormal{P}\subseteq\textnormal{NP}\subseteq\textnormal{PSPACE}</math>
| |
|
| |
| * <math>\textnormal{PSPACE}\subseteq\textnormal{NPSPACE}\subseteq\textnormal{EXP}\subseteq\textnormal{NEXP}\subseteq\textnormal{EXPSPACE}\subseteq\textnormal{NEXPSPACE}</math>
| |
|
| |
| }}
| |
|
| |
| \begin_hint
| |
| Skorzystaj z poznanych już własności klas oraz własności funkcji logarytmicznej, wielomianowej i wykładniczej.
| |
| \end_hint
| |
|
| |
| \begin_sol
| |
| Wszystkie zawierania pochodzą z wypisanych wcześniej ogólnych zależności. Nietrywialne, to:
| |
|
| |
| * <math>\textnormal{NL}\subseteq\textnormal{P}</math>, korzystamy z faktu, że <math>\textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})</math>, w tym wypadku
| |
| mamy bowiem <math>c^{\textnormal{log}n}=n^k</math>,
| |
|
| |
| * <math>\textnormal{NPSPACE}\subseteq\textnormal{EXP}</math>, również korzystamy z faktu, że <math>\textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})</math>, w tym wypadku
| |
| mamy bowiem <math>c^{n^k}=2^{n^{k'}}</math>.
| |
|
| |
| \end_sol
| |
|
| |
| Przyjrzyjmy się bliżej pierwszej serii relacji z poprzedniego ćwiczenia i zobrazujmy ją na rysunku:
| |
|
| |
| \vspace{1cm}
| |
| \begin_center
| |
| \includegraphics[width=10cm]{ZO-3-3-rys.jpg}<br>
| |
| Relacje pomiędzy podstawowymi klasami
| |
| \end_center
| |
| \vspace{1cm}
| |
|
| |
| <math>\textnormal{L}\subseteq\textnormal{NL}\subseteq\textnormal{P}\subseteq\textnormal{NP}\subseteq\textnormal{PSPACE}</math>
| |
| W następnej części z twierdzenia o hierarchii pamięciowej dowiemy się, że <math>L\varsubsetneq \textnormal{PSPACE}</math>. 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 <math>\textnormal{NSPACE}(f(n))\subseteq\textnormal{SPACE}(c^{f(n)})</math>. Okazuje
| |
| się, że zachodzi twierdzenie dużo silniejsze:
| |
|
| |
| {{twierdzenie|[Uzupelnij]||
| |
| (twierdzenie Savitcha)
| |
| Jeśli <math>f(n)</math> jest konstruowalna pamięciowo, to <math>\textnormal{NSPACE}(f(n))\subseteq\textnormal{SPACE}(f^2(n))</math>.
| |
| }}
| |
|
| |
| {{dowod|[Uzupelnij]||
| |
| Wspominaliśmy już o tym, że kluczowym elementem symulacji maszyny niedeterministycznej jest sprawdzanie czy istnieje ścieżka od konfiguracji początkowej do końcowej maszyny.
| |
| Problem sprawdzania czy dwa wierzchołki w grafie są połączone ścieżką jest znany jako REACHABILITY. Savitch udowodnił, że
| |
| REACHABILITY należy do SPACE(<math>\textnormal{log}^2n</math>), gdzie <math>n</math> to rozmiar grafu.
| |
| W naszym wypadku rozmiar grafu to liczba konfiguracji, czyli <math>c^{f(n)}</math>, zatem
| |
| REACHABILITY wymaga czasu <math>\textnormal{log}^2(c^{f(n)})=O(f(n))^2</math>, co da nam tezę.
| |
| Od tej pory przyjmijmy, że graf ma <math>n</math> wierzchołków.
| |
|
| |
| Wprowadźmy pomocniczą funkcję <math>\textnormal{PATH}(x,y,i)</math> która ma zwrócić 1, gdy istnieje ścieżka od <math>x</math> do <math>y</math> w grafie zawierająca co najwyżej <math>i</math>
| |
| wierzchołków. Nasze pytanie możemy przeformułować jako <math>PATH(b,e,n)</math>, gdzie <math>b</math> to stan początkowy, <math>e</math> końcowy, a <math>n</math> to
| |
| maksymalna długość ścieżki w grafie konfiguracji, czyli liczba wszystkich wierzchołków.
| |
|
| |
| Obliczymy <math>\textnormal{PATH}(x,y,i)</math> w sposób rekurencyjny. Jeśli <math>i=1</math> to sprawdzamy bezpośrednie przejście od konfiguracji <math>x</math> do <math>y</math>.
| |
| W przeciwnym wypadku najpierw wybieramy dowolny wierzchołek jako kandydata na wierzchołek pośredni na ścieżce pomiędzy <math>x</math> i <math>y</math>, który
| |
| oznaczmy przez <math>t</math>:
| |
|
| |
| \vspace{1cm}
| |
| \begin_center
| |
| \includegraphics[width=10cm]{ZO-3-4-rys.jpg}<br>
| |
| Wierzchołek pośredni
| |
| \end_center
| |
| \vspace{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,
| |
| w przeciwnym wypadku próbujemy kolejny wierzchołek <math>t</math>. Nie musimy się martwić o czas, tylko pamięć, więc policzmy ile jest nam potrzebne.
| |
|
| |
| Głębokość rekurencji wyniesie <math>\textnormal{log}n</math>, ze względu na fakt iż na każdym poziomie zmniejszamy długość o czynnik 2.
| |
| Aby zapamiętać wywołanie rekurencyjne (stos rekurencyjny) potrzebujemy pamiętać <math>x</math>, <math>y</math>, bieżące <math>t</math> oraz <math>i</math>. Wszystkie te liczby
| |
| w zapisie binarnym potrzebują <math>\textnormal{log}n</math> pamięci. Razem potrzebujemy <math>O(\textnormal{log}^2n)</math> pamięci.
| |
| }}
| |
|
| |
| 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!
| |
|
| |
| ===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>.
| |
| }}
| |
|
| |
| \begin_hint
| |
| Przeprowadź rozumowanie podobne jak w dowodzie twierdzenia o hierarchii pamięciowej.
| |
| \end_hint
| |
|
| |
| \begin_sol
| |
| 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.
| |
| \end_sol
| |
|
| |
| {{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>
| |
|
| |
| }}
| |
|
| |
| \begin_hint
| |
| Użyj poznanych twierdzeń o przyspieszaniu i hierarchii.
| |
| \end_hint
| |
|
| |
| \begin_sol<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.
| |
| \end_sol
| |
|
| |
| ==Testy końcowe==
| |
