|
|
| (Nie pokazano 32 wersji utworzonych przez 3 użytkowników) |
| Linia 1: |
Linia 1: |
| [section]
| |
|
| |
|
| {Lemma}
| |
|
| |
| {Twierdzenie}
| |
|
| |
| {Definicja}
| |
|
| |
| {Przykład}
| |
|
| |
| {Ćwiczenie}
| |
|
| |
| {Observation}
| |
|
| |
| {\hfill <math>\square</math>}
| |
|
| |
| {}
| |
|
| |
| {}
| |
|
| |
| \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
| |
|
| |
| {\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>.
| |
| }}
| |
|
| |
| {{\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.
| |
| 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.
| |
| }}
| |
|
| |
| {{\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
| |
| 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>?
| |
| }}
| |
|
| |
| {{\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:
| |
|
| |
| * 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.
| |
| }}
| |
|
| |
| 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>
| |
|
| |
| }}
| |
|
| |
| {{\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:
| |
|
| |
| * <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>.
| |
|
| |
| }}
| |
|
| |
| 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!
| |
