Test Arka: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Arek (dyskusja | edycje)
687 edycji
Arek (dyskusja | edycje)
687 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
Przedmiot & '''Złożoność obliczeniowa''' <br>
Przedmiot & '''Z³o¿ono¶æ obliczeniowa''' <br>


Moduł &  '''13''' <br>
Modu³ &  '''13''' <br>


Tytuł &  '''Pamięć logarytmiczna i hierarchia wielomianowa''' <br>
Tytu³ &  '''Pamiêæ logarytmiczna i hierarchia wielomianowa''' <br>


Opracowanie &  '''Przemysław Broniek''' <br>
Opracowanie &  '''Przemys³aw Broniek''' <br>


{ Syllabus}
{ Syllabus}


Pamięć logarytmiczna i hierarchia wielomianowa
Pamiêæ logarytmiczna i hierarchia wielomianowa


* klasy L, NL i coNL,
* klasy L, NL i coNL,
Linia 17: Linia 17:
* klasy coNP i DP,
* klasy coNP i DP,


* maszyny alternujące,
* maszyny alternuj±ce,


* hierarchia wielomianowa.
* hierarchia wielomianowa.
Linia 23: Linia 23:
==Klasy L, NL i coNL==
==Klasy L, NL i coNL==


W tym rozdziale zajmiemy się klasami złożoności, w których dajemy bardzo restrykcyjne wymagania odnośnie zużywanej
W tym rozdziale zajmiemy siê klasami z³o¿ono¶ci, w których dajemy bardzo restrykcyjne wymagania odno¶nie zu¿ywanej
pamięci, a mianowicie ograniczamy jej ilość przez funkcję logarytmiczną. Przypomnijmy:
pamiêci, a mianowicie ograniczamy jej ilo¶æ przez funkcjê logarytmiczn±. Przypomnijmy:


* Klasa L = SPACE(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(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 coNL = coNSPACE(log<math>n</math>), to dopełnienie klasy tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,
* Klasa coNL = coNSPACE(log<math>n</math>), to dope³nienie klasy tych jêzyków, które mog± byæ akceptowane w niedeterministycznej pamiêci logarytmicznej,


Na podstawie następnego rozdziału i twierdzenia Immermana-Szelepcsényi'ego dowiemy się, że NL=coNL . Natomiast pytanie czy L=NL pozostaje
Na podstawie nastêpnego rozdzia³u i twierdzenia Immermana-Szelepcsényi'ego dowiemy siê, ¿e NL=coNL . Natomiast pytanie czy L=NL pozostaje
wciąż problemem otwartym.
wci±¿ problemem otwartym.


Przyjrzymy się teraz problemom zupełnym w klasie NL. Zupełność definiujemy przy pomocy redukcji w pamięci logarytmicznej, gdyż
Przyjrzymy siê teraz problemom zupe³nym w klasie NL. Zupe³no¶æ definiujemy przy pomocy redukcji w pamiêci logarytmicznej, gdy¿
jak wiemy, wszystkie z powyższych klas są zawarte w klasie P (chociaż nie wiemy, czy ściśle). Dopuszczenie redukcji wielomianowej zniwelowałoby jakiekolwiek różnice pomiędzy językami,
jak wiemy, wszystkie z powy¿szych klas s± zawarte w klasie P (chocia¿ nie wiemy, czy ¶ci¶le). Dopuszczenie redukcji wielomianowej zniwelowa³oby jakiekolwiek ró¿nice pomiêdzy jêzykami,
gdyż sama redukcja miałaby moc obliczeniową pozwalającą rozwiązać wszystkie problemy z tych klas. Poniższy problem okazuje się być NL-zupełny:
gdy¿ sama redukcja mia³aby moc obliczeniow± pozwalaj±c± rozwi±zaæ wszystkie problemy z tych klas. Poni¿szy problem okazuje siê byæ NL-zupe³ny:


{{definicja|[Uzupelnij]||
{{definicja|[Uzupelnij]||
Problem REACHABILITY:<br>
Problem REACHABILITY:<br>
Wejście: Graf skierowany <math>G</math> oraz wierzchołki <math>x</math> i <math>y</math>.<br>
Wej¶cie: Graf skierowany <math>G</math> oraz wierzcho³ki <math>x</math> i <math>y</math>.<br>
Wyjście: Czy istnieje ścieżka od <math>x</math> do <math>y</math> w <math>G</math>?
Wyj¶cie: Czy istnieje ¶cie¿ka od <math>x</math> do <math>y</math> w <math>G</math>?
}}
}}


{{cwiczenie||
{{cwiczenie||
Pokaż, że problem REACHABILITY jest NL-zupełny.
Poka¿, ¿e problem REACHABILITY jest NL-zupe³ny.
}}
}}


{{wskazowka|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none">
Zwróć uwagę na fakt, że problem REACHABILITY jest związany z wykonywaniem obliczeń przez maszynę Turinga.
Zwróæ uwagê na fakt, ¿e problem REACHABILITY jest zwi±zany z wykonywaniem obliczeñ przez maszynê Turinga.
}}
</div>}}</div>


{{rozwiazanie||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none">
Pokażmy najpierw, że problem REACHABILITY należy do NL.
Poka¿my najpierw, ¿e problem REACHABILITY nale¿y do NL.
Użyjemy dwóch zmiennych <math>v</math> - wierzchołek bieżący, oraz <math>u</math> wierzchołek kolejny na ścieżce od <math>x</math> do <math>y</math>.
U¿yjemy dwóch zmiennych <math>v</math> - wierzcho³ek bie¿±cy, oraz <math>u</math> wierzcho³ek kolejny na ¶cie¿ce od <math>x</math> do <math>y</math>.


Początkowo
Pocz±tkowo
ustawiamy <math>v:=x</math>. Ponieważ mamy do dyspozycji niedeterminizm to zgadujemy wierzchołek <math>u</math> i sprawdzamy, czy jest sąsiedni do <math>v</math>.
ustawiamy <math>v:=x</math>. Poniewa¿ mamy do dyspozycji niedeterminizm to zgadujemy wierzcho³ek <math>u</math> i sprawdzamy, czy jest s±siedni do <math>v</math>.
Jeśli nie, to przerywamy obliczenie, wiedząc, że na innej ścieżce obliczeń przetworzymy inne możliwości.
Je¶li nie, to przerywamy obliczenie, wiedz±c, ¿e na innej ¶cie¿ce obliczeñ przetworzymy inne mo¿liwo¶ci.
Jeśli jest sąsiedni to sprawdzamy czy <math>u=y</math> co oznacza, że dotarliśmy do celu i akceptujemy parę <math>x</math>, <math>y</math>. W przeciwnym wypadku
Je¶li jest s±siedni to sprawdzamy czy <math>u=y</math> co oznacza, ¿e dotarli¶my do celu i akceptujemy parê <math>x</math>, <math>y</math>. W przeciwnym wypadku
ustawiamy <math>v:=u</math> i kontynuujemy obliczenia.
ustawiamy <math>v:=u</math> i kontynuujemy obliczenia.


Formalnie należy jeszcze użyć trzeciej zmiennej <math>licznik</math>, która zlicza liczbę kroków, tak aby ostatecznie
Formalnie nale¿y jeszcze u¿yæ trzeciej zmiennej <math>licznik</math>, która zlicza liczbê kroków, tak aby ostatecznie
odrzucić parę, gdy <math>licznik</math> przekroczy liczbę wierzchołków grafu. Użyliśmy pamięci rzędu log <math>n</math> co kończy dowód pierwszego faktu.
odrzuciæ parê, gdy <math>licznik</math> przekroczy liczbê wierzcho³ków grafu. U¿yli¶my pamiêci rzêdu log <math>n</math> co koñczy dowód pierwszego faktu.


Teraz musimy pokazać, że każdy inny problem z klasy NL redukuje się do REACHABILITY
Teraz musimy pokazaæ, ¿e ka¿dy inny problem z klasy NL redukuje siê do REACHABILITY
poprzez redukcję w pamięci logarytmicznej. Weźmy dowolny język L z klasy NL i odpowiadającą mu niedeterministyczną maszynę Turinga
poprzez redukcjê w pamiêci logarytmicznej. We¼my dowolny jêzyk L z klasy NL i odpowiadaj±c± mu niedeterministyczn± maszynê Turinga
<math>M</math>.
<math>M</math>.


Rozmiar grafu konfiguracji maszyny działającej w pamięci log <math>n</math> to jak wiemy <math>c^{</math> log <math>n}\in O(n)</math>,
Rozmiar grafu konfiguracji maszyny dzia³aj±cej w pamiêci log <math>n</math> to jak wiemy <math>c^{</math> log <math>n}\in O(n)</math>,
natomiast sprawdzenie czy <math>x</math> jest akceptowany przez <math>M</math> możemy sprowadzić do istnienia ścieżki od konfiguracji początkowej
natomiast sprawdzenie czy <math>x</math> jest akceptowany przez <math>M</math> mo¿emy sprowadziæ do istnienia ¶cie¿ki od konfiguracji pocz±tkowej
do akceptującej. Jest to zatem instancja problemu REACHABILITY na danych wielkości rzędu <math>n</math> .
do akceptuj±cej. Jest to zatem instancja problemu REACHABILITY na danych wielko¶ci rzêdu <math>n</math> .
Nie potrzebujemy konstruować całego grafu, a jedynie stwierdzać, czy dwie konfiguracje są sąsiednie, co możemy zrobić
Nie potrzebujemy konstruowaæ ca³ego grafu, a jedynie stwierdzaæ, czy dwie konfiguracje s± s±siednie, co mo¿emy zrobiæ
w pamięci logarytmicznej.
w pamiêci logarytmicznej.
}}
</div>}}</div>


Bardzo ciekawy rezultat, który zbliżył nas do odpowiedzi na pytanie czy L=NL, uzyskał w 2004 Reingold. Pokazał on, że
Bardzo ciekawy rezultat, który zbli¿y³ nas do odpowiedzi na pytanie czy L=NL, uzyska³ w 2004 Reingold. Pokaza³ on, ¿e
problem UNDIRECTED REACHABILITY, czyli osiągalność w grafie ''nieskierowanym'' należy do klasy L.
problem UNDIRECTED REACHABILITY, czyli osi±galno¶æ w grafie ''nieskierowanym'' nale¿y do klasy L.


==Twierdzenie Immermana-Szelepcsényi'ego==
==Twierdzenie Immermana-Szelepcsényi'ego==


Ten rozdział poświęcony jest bardzo ciekawemu i całkiem młodemu wynikowi udowodnionemu niezależnie
Ten rozdzia³ po¶wiêcony jest bardzo ciekawemu i ca³kiem m³odemu wynikowi udowodnionemu niezale¿nie
przez Neila Immermana i Róberta Szelepcsényi'ego w roku 1987, za który otrzymali w 1995 nagrodę Gödel'a.
przez Neila Immermana i Róberta Szelepcsényi'ego w roku 1987, za który otrzymali w 1995 nagrodê Gödel'a.


Twierdzenie mówi o tym, że klasy niedeterministyczne złożoności pamięciowej są zamknięte na dopełnienie:
Twierdzenie mówi o tym, ¿e klasy niedeterministyczne z³o¿ono¶ci pamiêciowej s± zamkniête na dope³nienie:


{{twierdzenie|Immermana-Szelepcsényi'ego||}}
{{twierdzenie|[Uzupelnij]||
Jeśli <math>f(n)</math> jest konstruowalna pamięciowo, to NSPACE(f(n))=coNSPACE(f(n)).
(twierdzenie Immermana-Szelepcsényi'ego)
Je¶li <math>f(n)</math> jest konstruowalna pamiêciowo, to NSPACE(f(n))=coNSPACE(f(n)).
}}


{{dowod|||}}
{{dowod|[Uzupelnij]||
To co zostało pokazane przez autorów, to maszyna niedeterministyczna, która mając dany graf skierowany <math>G</math> i
To co zosta³o pokazane przez autorów, to maszyna niedeterministyczna, która maj±c dany graf skierowany <math>G</math> i
wierzchołek <math>x</math> potrafi obliczyć liczbę wierzchołków osiąganych z <math>x</math> w grafie <math>G</math> przy użyciu pamięci log <math>n</math>.
wierzcho³ek <math>x</math> potrafi obliczyæ liczbê wierzcho³ków osi±ganych z <math>x</math> w grafie <math>G</math> przy u¿yciu pamiêci log <math>n</math>.
Zrobimy z niej użytek w ostatniej części głównego dowodu, gdy będziemy uruchamiać ją na grafie konfiguracji.
Zrobimy z niej u¿ytek w ostatniej czê¶ci g³ównego dowodu, gdy bêdziemy uruchamiaæ j± na grafie konfiguracji.


Maszyna jest dosyć trikowa i pokazuje jak wiele daje nam niedeterminizm. Wielokrotnie będziemy wykorzystywać fakt,
Maszyna jest dosyæ trikowa i pokazuje jak wiele daje nam niedeterminizm. Wielokrotnie bêdziemy wykorzystywaæ fakt,
że wystarczy nam, aby maszyna niedeterministyczna na dowolnej ścieżce dokonała poprawnego obliczenia. Na wszystkich pozostałych ścieżkach
¿e wystarczy nam, aby maszyna niedeterministyczna na dowolnej ¶cie¿ce dokona³a poprawnego obliczenia. Na wszystkich pozosta³ych ¶cie¿kach
będziemy "wykrywać", że coś jest nie tak i kończyć działanie w stanie odrzucającym ("poddawać się").
bêdziemy "wykrywaæ", ¿e co¶ jest nie tak i koñczyæ dzia³anie w stanie odrzucaj±cym ("poddawaæ siê").


Oznaczmy, przez <math>S(k)</math> zbiór tych wierzchołków grafu <math>G</math>, które są osiągane z <math>x</math> ścieżką o długości co najwyżej <math>k</math>. Natomiast
Oznaczmy, przez <math>S(k)</math> zbiór tych wierzcho³ków grafu <math>G</math>, które s± osi±gane z <math>x</math> ¶cie¿k± o d³ugo¶ci co najwy¿ej <math>k</math>. Natomiast
przez <math>s(k)=|S(k)|</math> oznaczymy liczność tego zbioru. Naszym obiektem zainteresowania jest zatem obliczenie wartości <math>s(n)</math>,
przez <math>s(k)=|S(k)|</math> oznaczymy liczno¶æ tego zbioru. Naszym obiektem zainteresowania jest zatem obliczenie warto¶ci <math>s(n)</math>,
czyli liczba wszystkich wierzchołków osiągalnych, gdyż <math>n</math> -- rozmiar grafu -- ogranicza długość ścieżki.
czyli liczba wszystkich wierzcho³ków osi±galnych, gdy¿ <math>n</math> -- rozmiar grafu -- ogranicza d³ugo¶æ ¶cie¿ki.


Pamiętamy jednak, że mamy do dyspozycji tylko logarytmiczną ilość pamięci, więc o zapamiętaniu zbioru <math>S(k)</math> (i obliczaniu na jego podstawie
Pamiêtamy jednak, ¿e mamy do dyspozycji tylko logarytmiczn± ilo¶æ pamiêci, wiêc o zapamiêtaniu zbioru <math>S(k)</math> (i obliczaniu na jego podstawie
<math>S(k+1)</math> co byłoby banalne) nie możemy marzyć - ma on wielkość
<math>S(k+1)</math> co by³oby banalne) nie mo¿emy marzyæ - ma on wielko¶æ
liniową względem rozmiaru <math>G</math>. To brzmi niesamowicie, ale będziemy obliczać <math>s(k+1)</math> na podstawie <math>s(k)</math>! Czyli wystarczy nam liczba
liniow± wzglêdem rozmiaru <math>G</math>. To brzmi niesamowicie, ale bêdziemy obliczaæ <math>s(k+1)</math> na podstawie <math>s(k)</math>! Czyli wystarczy nam liczba
stosownych wierzchołków, która to do zapisu potrzebuje pamięci logarytmicznej. Główna pętla algorytmu przedstawia się następująco:
stosownych wierzcho³ków, która to do zapisu potrzebuje pamiêci logarytmicznej. G³ówna pêtla algorytmu przedstawia siê nastêpuj±co:


{<math>s(0):=1</math>}
{<math>s(0):=1</math>}
Linia 112: Linia 114:
{Wyznacz <math>s(i)</math> na podstawie <math>s(i-1)</math>}
{Wyznacz <math>s(i)</math> na podstawie <math>s(i-1)</math>}


Teraz procedura obliczająca <math>s(i)</math>. Jest ona całkiem prosta, jeśli zastosujemy w niej pewien skrót notacyjny:
Teraz procedura obliczaj±ca <math>s(i)</math>. Jest ona ca³kiem prosta, je¶li zastosujemy w niej pewien skrót notacyjny:


{<math>s(i):=0</math>}
{<math>s(i):=0</math>}
Linia 118: Linia 120:
{<math>v\in S(i)</math>}{s(i)++}
{<math>v\in S(i)</math>}{s(i)++}


Lecz zbioru <math>S(i)</math> nie byliśmy w stanie zapamiętać. Zapowiedzielśmy już, że będziemy sprawdzać, czy wierzchołek do niego należy,
Lecz zbioru <math>S(i)</math> nie byli¶my w stanie zapamiêtaæ. Zapowiedziel¶my ju¿, ¿e bêdziemy sprawdzaæ, czy wierzcho³ek do niego nale¿y,
na podstawie <math>s(i-1)</math>. To najbardziej skomplikowana część algorytmu, gdzie wykorzystujemy niedeterminizm.
na podstawie <math>s(i-1)</math>. To najbardziej skomplikowana czê¶æ algorytmu, gdzie wykorzystujemy niedeterminizm.


Przeglądniemy teraz wszystkie wierzchołki <math>u</math> grafu <math>G</math> i sprawdzimy, czy któryś z nich należy do <math>S(i-1)</math> w sposób niedeterministyczny.
Przegl±dniemy teraz wszystkie wierzcho³ki <math>u</math> grafu <math>G</math> i sprawdzimy, czy który¶ z nich nale¿y do <math>S(i-1)</math> w sposób niedeterministyczny.
Przypomnijmy, że taka procedura, gdy mówi "TAK", to wierzchołek na pewno należy do <math>S(i-1)</math>, natomiast gdy mówi "NIE" to mogliśmy trafić na nieodpowiednią
Przypomnijmy, ¿e taka procedura, gdy mówi "TAK", to wierzcho³ek na pewno nale¿y do <math>S(i-1)</math>, natomiast gdy mówi "NIE" to mogli¶my trafiæ na nieodpowiedni±
ścieżkę obliczeń. Będziemy jednak zliczać ile wierzchołków zgadliśmy na TAK i sprawdzimy, czy wyjdzie nam <math>s(i-1)</math>. Jeśli tak się stanie, to będziemy mieć gwarancję, że
¶cie¿kê obliczeñ. Bêdziemy jednak zliczaæ ile wierzcho³ków zgadli¶my na TAK i sprawdzimy, czy wyjdzie nam <math>s(i-1)</math>. Je¶li tak siê stanie, to bêdziemy mieæ gwarancjê, ¿e
o każdym wierzchołku <math>u</math> zgadliśmy dobrze. Jeśli wyszło nam mniej, to odrzucamy, wiedząc, że na innej ścieżce obliczeń musi nam się udać.
o ka¿dym wierzcho³ku <math>u</math> zgadli¶my dobrze. Je¶li wysz³o nam mniej, to odrzucamy, wiedz±c, ¿e na innej ¶cie¿ce obliczeñ musi nam siê udaæ.
Następnie sprawdzamy, czy z <math>u</math> można dojść do <math>v</math> przy pomocy jednej krawędzi w ten sposób obliczymy
Nastêpnie sprawdzamy, czy z <math>u</math> mo¿na doj¶æ do <math>v</math> przy pomocy jednej krawêdzi w ten sposób obliczymy
czy <math>v\in S(i)</math>:
czy <math>v\in S(i)</math>:


Linia 136: Linia 138:
{<math>licznik<s(i-1)</math>}{NIE} {wynik}  
{<math>licznik<s(i-1)</math>}{NIE} {wynik}  


Teraz przejdźmy do konstrukcji maszyny obliczającej, czy <math>u\in S(i-1)</math> w sposób niedeterministyczny. Algorytm jest całkiem prosty i podobny do tego, w którym
Teraz przejd¼my do konstrukcji maszyny obliczaj±cej, czy <math>u\in S(i-1)</math> w sposób niedeterministyczny. Algorytm jest ca³kiem prosty i podobny do tego, w którym
pokazywaliśmy, że REACHABILITY jest w NL.
pokazywali¶my, ¿e REACHABILITY jest w NL.
Zgadujemy sekwencję <math>k-1</math> wierzchołków. Rozpoczynamy od <math>x</math>. Sprawdzamy, czy każdy kolejny wierzchołek jest sąsiadem poprzedniego (lub równy poprzedniemu)
Zgadujemy sekwencjê <math>k-1</math> wierzcho³ków. Rozpoczynamy od <math>x</math>. Sprawdzamy, czy ka¿dy kolejny wierzcho³ek jest s±siadem poprzedniego (lub równy poprzedniemu)
oraz czy w końcu dochodzimy do <math>u</math>. W ten sposób sprawdzimy (niedeterministycznie) wszystkie ścieżki długości co najwyżej <math>i-1</math>.
oraz czy w koñcu dochodzimy do <math>u</math>. W ten sposób sprawdzimy (niedeterministycznie) wszystkie ¶cie¿ki d³ugo¶ci co najwy¿ej <math>i-1</math>.


Poniżej zapis algorytmu dla sytuacji ścieżki długości <math>k</math>:
Poni¿ej zapis algorytmu dla sytuacji ¶cie¿ki d³ugo¶ci <math>k</math>:


{<math>p_1:=x</math>}
{<math>p_1:=x</math>}
Linia 150: Linia 152:
{<math>p_k=u</math>}{TAK} {NIE}  
{<math>p_k=u</math>}{TAK} {NIE}  


To już koniec algorytmu. Krótka analiza wykazuje, że w trakcie jego działania musimy pamiętać jedynie skończoną liczbę
To ju¿ koniec algorytmu. Krótka analiza wykazuje, ¿e w trakcie jego dzia³ania musimy pamiêtaæ jedynie skoñczon± liczbê
wierzchołków i liczb wielkości co najwyżej <math>n</math> zatem działa on w pamięci logarytmicznej.
wierzcho³ków i liczb wielko¶ci co najwy¿ej <math>n</math> zatem dzia³a on w pamiêci logarytmicznej.


Przejdźmy zatem do wykorzystania maszyny do udowodnienia tezy naszego twierdzenia. Weźmy język <math>L</math> należący do NSPACE(<math>f(n)</math>), gdzie
Przejd¼my zatem do wykorzystania maszyny do udowodnienia tezy naszego twierdzenia. We¼my jêzyk <math>L</math> nale¿±cy do NSPACE(<math>f(n)</math>), gdzie
<math>f(n)\geqslant </math> log <math>n</math>, gdyż <math>f(n)</math> jest konstruowalna pamięciowo. Istnieje zatem maszyna niedeterministyczna <math>M</math> akceptująca
<math>f(n)\geqslant </math> log <math>n</math>, gdy¿ <math>f(n)</math> jest konstruowalna pamiêciowo. Istnieje zatem maszyna niedeterministyczna <math>M</math> akceptuj±ca
<math>L</math> w pamięci niedeterministycznej. Musimy pokazać, że istnieje maszyna niedeterministyczna <math>\overline{M}</math> akceptująca <math>\overline{L}</math> również
<math>L</math> w pamiêci niedeterministycznej. Musimy pokazaæ, ¿e istnieje maszyna niedeterministyczna <math>\overline{M}</math> akceptuj±ca <math>\overline{L}</math> równie¿
w pamięci <math>f(n)</math>. Bierzemy graf konfiguracji <math>M</math> dla słowa wejściowego <math>x</math>. Musimy stwierdzić, czy nie istnieje ścieżka od
w pamiêci <math>f(n)</math>. Bierzemy graf konfiguracji <math>M</math> dla s³owa wej¶ciowego <math>x</math>. Musimy stwierdziæ, czy nie istnieje ¶cie¿ka od
konfiguracji początkowej do akceptującej. Wtedy bowiem <math>x\notin L</math> czyli <math>M'</math> ma zaakceptować <math>x</math>.
konfiguracji pocz±tkowej do akceptuj±cej. Wtedy bowiem <math>x\notin L</math> czyli <math>M'</math> ma zaakceptowaæ <math>x</math>.


Oznaczmy konfigurację akceptującą przez <math>y</math>.
Oznaczmy konfiguracjê akceptuj±c± przez <math>y</math>.
Liczymy zatem zbiór <math>S(n)</math> dla grafu konfiguracji przy pomocy algorytmu z pierwszej części dowodu.
Liczymy zatem zbiór <math>S(n)</math> dla grafu konfiguracji przy pomocy algorytmu z pierwszej czê¶ci dowodu.
Jeśli algorytm zakończy się wynikiem pozytywnym, to oznacza to, że <math>s(n)</math> jest policzone
Je¶li algorytm zakoñczy siê wynikiem pozytywnym, to oznacza to, ¿e <math>s(n)</math> jest policzone
poprawnie. Jeśli zatem w trakcie przeglądania nie zakwalifikowaliśmy wierzchołka <math>y</math> do żadnego ze zbiorów
poprawnie. Je¶li zatem w trakcie przegl±dania nie zakwalifikowali¶my wierzcho³ka <math>y</math> do ¿adnego ze zbiorów
<math>S(i)</math> to znaczy, że ''nie'' jest on osiągalny.
<math>S(i)</math> to znaczy, ¿e ''nie'' jest on osi±galny.


W tej sytuacji maszyna <math>M'</math> może zaakceptować słowo <math>x</math>, które
W tej sytuacji maszyna <math>M'</math> mo¿e zaakceptowaæ s³owo <math>x</math>, które
nie należy do <math>L</math>, a tym samym pokazujemy, że <math>L\in </math> coNSPACE <math>(f(n))</math>.
nie nale¿y do <math>L</math>, a tym samym pokazujemy, ¿e <math>L\in </math> coNSPACE <math>(f(n))</math>.
}}


==Klasy coNP i DP==
==Klasy coNP i DP==


Wprowadziliśmy już zarówno klasę NP jak i pojęcie dopełnień klas. Przyjrzyjmy się bliżej klasie coNP.
Wprowadzili¶my ju¿ zarówno klasê NP jak i pojêcie dope³nieñ klas. Przyjrzyjmy siê bli¿ej klasie coNP.
Klasa NP, jest to zbiór tych języków, dla których możemy łatwo weryfikować przynależność słów.
Klasa NP, jest to zbiór tych jêzyków, dla których mo¿emy ³atwo weryfikowaæ przynale¿no¶æ s³ów.
Klasa coNP natomiast, to zbiór tych języków, dla których możemy łatwo weryfikować, że słowo nie należy do języka.
Klasa coNP natomiast, to zbiór tych jêzyków, dla których mo¿emy ³atwo weryfikowaæ, ¿e s³owo nie nale¿y do jêzyka.


Podobnie jak dla NP i twierdzenia Fagina, można scharakteryzować coNP jako zbiór własności teoriografowych wyrażalnych
Podobnie jak dla NP i twierdzenia Fagina, mo¿na scharakteryzowaæ coNP jako zbiór w³asno¶ci teoriografowych wyra¿alnych
w ''uniwersalnej'' logice drugiego rzędu.
w ''uniwersalnej'' logice drugiego rzêdu.


Oto przykłady problemów z klasy coNP:
Oto przyk³ady problemów z klasy coNP:


{{definicja|[Uzupelnij]||
{{definicja|[Uzupelnij]||
Problem TAUTOLOGY:<br>
Problem TAUTOLOGY:<br>
Wejście: formuła logiczna <math>\phi</math> jak dla problemu SAT.<br>
Wej¶cie: formu³a logiczna <math>\phi</math> jak dla problemu SAT.<br>
Wyjście: czy każde wartościowanie spełnia <math>\phi</math>?
Wyj¶cie: czy ka¿de warto¶ciowanie spe³nia <math>\phi</math>?
}}
}}


{{definicja|[Uzupelnij]||
{{definicja|[Uzupelnij]||
Problem HAMILTON PATH COMPLEMENT:<br>
Problem HAMILTON PATH COMPLEMENT:<br>
Wejście: graf nieskierowany <math>G</math>.<br>
Wej¶cie: graf nieskierowany <math>G</math>.<br>
Wyjście: czy <math>G</math> nie zawiera ścieżki Hamiltona?
Wyj¶cie: czy <math>G</math> nie zawiera ¶cie¿ki Hamiltona?
}}
}}


W powyższych problemach weryfikacja negatywna słowa wejściowego jest łatwa,
W powy¿szych problemach weryfikacja negatywna s³owa wej¶ciowego jest ³atwa,
bo opiera się na zgadnięciu wartościowania niespełniającego lub ścieżki Hamiltona.
bo opiera siê na zgadniêciu warto¶ciowania niespe³niaj±cego lub ¶cie¿ki Hamiltona.


Nietrudno udowodnić (patrz ćwiczenie końcowe), że są to problemy zupełne dla klasy coNP.
Nietrudno udowodniæ (patrz æwiczenie koñcowe), ¿e s± to problemy zupe³ne dla klasy coNP.
Nie jest to nic zaskakującego, bowiem równie prosto można udowodnić,
Nie jest to nic zaskakuj±cego, bowiem równie prosto mo¿na udowodniæ,
że jeżeli <math>L</math> jest NP-zupełny, to jego dopełnienie <math>\overline{L}</math> jest coNP-zupełne.
¿e je¿eli <math>L</math> jest NP-zupe³ny, to jego dope³nienie <math>\overline{L}</math> jest coNP-zupe³ne.


Jak wiele pytań w teorii złożoności obliczeniowej również i to, czy NP=coNP pozostaje otwarte.
Jak wiele pytañ w teorii z³o¿ono¶ci obliczeniowej równie¿ i to, czy NP=coNP pozostaje otwarte.
Możemy jedynie stwierdzić, że jeżeli P=NP, to NP=coNP, gdyż P jest zamknięta na dopełnienie.
Mo¿emy jedynie stwierdziæ, ¿e je¿eli P=NP, to NP=coNP, gdy¿ P jest zamkniêta na dope³nienie.
Jednak już implikacja w drugą stronę nie jest znana. Inna podobna implikacja to:
Jednak ju¿ implikacja w drug± stronê nie jest znana. Inna podobna implikacja to:


{{cwiczenie||
{{cwiczenie||
Jeśli <math>L</math> jest coNP-zupełny i <math>L\in NP</math> to <math>NP=coNP</math>.
Je¶li <math>L</math> jest coNP-zupe³ny i <math>L\in NP</math> to NP=coNP.
}}
}}


{{wskazowka|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none">
Pokaż inkluzje w obie strony korzystając z symetrii klas.
Poka¿ inkluzje w obie strony korzystaj±c z symetrii klas.
}}
</div>}}</div>


{{rozwiazanie||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none">
Ustalmy <math>L</math> z klasy NP, który jest coNP-zupełny.
Ustalmy <math>L</math> z klasy NP, który jest coNP-zupe³ny.


Weźmy dowolny <math>L'</math> z klasy coNP.
We¼my dowolny <math>L'</math> z klasy coNP.
Ponieważ <math>L</math> jest coNP-zupełny, więc <math>L'</math> redukuje się do <math>L</math>, czyli
Poniewa¿ <math>L</math> jest coNP-zupe³ny, wiêc <math>L'</math> redukuje siê do <math>L</math>, czyli
<math>L'</math> należy do NP, bowiem redukcja jest procedurą deterministyczną.
<math>L'</math> nale¿y do NP, bowiem redukcja jest procedur± deterministyczn±.


Analogicznie, weźmy dowolny <math>L'</math> z NP. Wiemy, że <math>\overline{L}</math> jest NP-zupełny,
Analogicznie, we¼my dowolny <math>L'</math> z NP. Wiemy, ¿e <math>\overline{L}</math> jest NP-zupe³ny,
i należy do coNP. Możemy zatem sprowadzić <math>L'</math> redukcją do <math>\overline{L}</math>.
i nale¿y do coNP. Mo¿emy zatem sprowadziæ <math>L'</math> redukcj± do <math>\overline{L}</math>.
Zatem <math>L'</math> należy do coNP.
Zatem <math>L'</math> nale¿y do coNP.
}}
</div>}}</div>


Poniższy rysunek przedstawia relacje pomiędzy poznanymi klasami i omawianą za chwilę klasą DP:
Poni¿szy rysunek przedstawia relacje pomiêdzy poznanymi klasami i omawian± za chwilê klas± DP:


{1cm}
{1cm}


[width=10cm]{ZO-13-1-rys.jpg}<br>
[width=10cm]{ZO-13-1-rys.jpg}<br>
Relacje pomiędzy klasami NP, coNP i DP
Relacje pomiêdzy klasami NP, coNP i DP


{1cm}
{1cm}


Oczywiście przyglądając się wszystkim takim rysunkom należy pamiętać, że mogą one w wielu miejscach
Oczywi¶cie przygl±daj±c siê wszystkim takim rysunkom nale¿y pamiêtaæ, ¿e mog± one w wielu miejscach
kolapsować.
kolapsowaæ.


===Klasa DP===
===Klasa DP===


Zastanówmy się nad następującym problemem:
Zastanówmy siê nad nastêpuj±cym problemem:


{{przyklad|[Uzupelnij]||
{{przyklad|[Uzupelnij]||
Problem EXACT TSP:<br>
Problem EXACT TSP:<br>
Wejście: graf nieskierowany ważony <math>G</math> i liczba <math>K</math> <br>
Wej¶cie: graf nieskierowany wa¿ony <math>G</math> i liczba <math>K</math> <br>
Wyjście: czy optymalna trasa komiwojażera dla <math>G</math> ma wartość dokładnie <math>K</math>?
Wyj¶cie: czy optymalna trasa komiwoja¿era dla <math>G</math> ma warto¶æ dok³adnie <math>K</math>?
}}
}}


Jest to wersja dokładna znanego problemu optymalizacyjnego -- problemu komiwojażera. Wiemy że wersja decyzyjna TSP(D) jest NP-zupełna.
Jest to wersja dok³adna znanego problemu optymalizacyjnego -- problemu komiwoja¿era. Wiemy ¿e wersja decyzyjna TSP(D) jest NP-zupe³na.
Nietrudno pokazać również, że EXACT TSP i TSP(D) są wielomianowo równoważne (ćwiczenie końcowe), tzn., że jeśli jeden z nich ma rozwiązanie w czasie
Nietrudno pokazaæ równie¿, ¿e EXACT TSP i TSP(D) s± wielomianowo równowa¿ne (æwiczenie koñcowe), tzn., ¿e je¶li jeden z nich ma rozwi±zanie w czasie
wielomianowym to drugi też. W tym rozdziale
wielomianowym to drugi te¿. W tym rozdziale
sklasyfikujemy złożoność EXACT TSP dokładniej przy pomocy klasy DP. Nie umiemy bowiem pokazać, że EXACT TSP należy do NP, wszak
sklasyfikujemy z³o¿ono¶æ EXACT TSP dok³adniej przy pomocy klasy DP. Nie umiemy bowiem pokazaæ, ¿e EXACT TSP nale¿y do NP, wszak
jak poświadczyć i szybko zweryfikować, że długość optymalnej trasy wynosi dokładnie <math>K</math>? Widzimy, że odpowiedź na to pytanie wymaga
jak po¶wiadczyæ i szybko zweryfikowaæ, ¿e d³ugo¶æ optymalnej trasy wynosi dok³adnie <math>K</math>? Widzimy, ¿e odpowied¼ na to pytanie wymaga
stwierdzenia, że trasa ma długość co najmniej <math>K</math> i co najwyżej <math>K</math>, co sugeruje pewne specyficzne połączenie problemu TSP(D) i jego dopełnienia.
stwierdzenia, ¿e trasa ma d³ugo¶æ co najmniej <math>K</math> i co najwy¿ej <math>K</math>, co sugeruje pewne specyficzne po³±czenie problemu TSP(D) i jego dope³nienia.


{{definicja|[Uzupelnij]||
{{definicja|[Uzupelnij]||
Klasa DP to zbiór języków <math>L</math> takich, że <math>L=L_1\cap L_2</math>, gdzie <math>L_1\in NP</math> natomiast <math>L_2 \in coNP</math>.
Klasa DP to zbiór jêzyków <math>L</math> takich, ¿e <math>L=L_1\cap L_2</math>, gdzie <math>L_1\in NP</math> natomiast <math>L_2 \in coNP</math>.
}}
}}


Przy tak postawionej definicji EXACT TSP należy do DP. Jest on bowiem przecięciem języka TSP(D) i TSP(D) COMPLEMENT, tzn. koszt trasy wynosi dokładnie
Przy tak postawionej definicji EXACT TSP nale¿y do DP. Jest on bowiem przeciêciem jêzyka TSP(D) i TSP(D) COMPLEMENT, tzn. koszt trasy wynosi dok³adnie
<math>K</math>, gdy jest równy co najwyżej <math>K</math> (to przynależność do TSP(D)) oraz co najmniej <math>K</math> (to przynależność słowa do TSP(D) COMPLEMENT).
<math>K</math>, gdy jest równy co najwy¿ej <math>K</math> (to przynale¿no¶æ do TSP(D)) oraz co najmniej <math>K</math> (to przynale¿no¶æ s³owa do TSP(D) COMPLEMENT).


Klasa DP posiada problemy zupełne. Rozważmy problem następujący:
Klasa DP posiada problemy zupe³ne. Rozwa¿my problem nastêpuj±cy:


{{przyklad|[Uzupelnij]||
{{przyklad|[Uzupelnij]||
Problem SAT-UNSAT:<br>
Problem SAT-UNSAT:<br>
Wejście: formuły logiczne <math>\phi</math> i <math>\psi</math> jak dla SAT.<br>
Wej¶cie: formu³y logiczne <math>\phi</math> i <math>\psi</math> jak dla SAT.<br>
Wyjście: czy formuła <math>\phi</math> jest spełnialna, natomiast <math>\psi</math> niespełnialna?
Wyj¶cie: czy formu³a <math>\phi</math> jest spe³nialna, natomiast <math>\psi</math> niespe³nialna?
}}
}}


{{cwiczenie||
{{cwiczenie||
Udowodnij, że problem SAT-UNSAT jest DP-zupełny.
Udowodnij, ¿e problem SAT-UNSAT jest DP-zupe³ny.
}}
}}


{{wskazowka|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none">
Skorzystaj z redukcji języka z NP oraz dopełnienia języka z coNP do SAT.
Skorzystaj z redukcji jêzyka z NP oraz dope³nienia jêzyka z coNP do SAT.
}}
</div>}}</div>


{{rozwiazanie||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none">
Najpierw pokażmy, że SAT-UNSAT należy do klasy DP. Musimy wskazać stosowne języki <math>L_1</math> i <math>L_2</math> odpowiednio z klas NP i coNP.
Najpierw poka¿my, ¿e SAT-UNSAT nale¿y do klasy DP. Musimy wskazaæ stosowne jêzyki <math>L_1</math> i <math>L_2</math> odpowiednio z klas NP i coNP.
Wybieramy <math>L_1=\{(\phi,\psi):\phi</math>  jest spełnialna <math>\}</math> oraz  <math>L_1=\{(\phi,\psi):\psi</math>  nie jest spełnialna <math>\}</math>, o których
Wybieramy <math>L_1=\{(\phi,\psi):\phi</math>  jest spe³nialna <math>\}</math> oraz  <math>L_1=\{(\phi,\psi):\psi</math>  nie jest spe³nialna <math>\}</math>, o których
można to łatwo stwierdzić.
mo¿na to ³atwo stwierdziæ.


Przejdźmy do części związanej z pokazaniem redukcji z dowolnego problemu z klasy DP. Weźmy <math>L\in</math> DP. Wiemy, że
Przejd¼my do czê¶ci zwi±zanej z pokazaniem redukcji z dowolnego problemu z klasy DP. We¼my <math>L\in</math> DP. Wiemy, ¿e
<math>L=L_1\cap L_2</math> i na mocy własności klas NP i coNP istnieją redukcje <math>R_1</math> języka <math>L_1</math> do SAT oraz <math>R2</math>
<math>L=L_1\cap L_2</math> i na mocy w³asno¶ci klas NP i coNP istniej± redukcje <math>R_1</math> jêzyka <math>L_1</math> do SAT oraz <math>R2</math>
dopełnienia języka <math>L_2</math> do SAT (jako że <math>L_2</math> jest w coNP). Definiujemy redukcję jako <math>R(x)=(R_1(x),R_2(x))</math>.
dope³nienia jêzyka <math>L_2</math> do SAT (jako ¿e <math>L_2</math> jest w coNP). Definiujemy redukcjê jako <math>R(x)=(R_1(x),R_2(x))</math>.


Na podstawie konstrukcji wiemy, że <math>x\in L_1</math>, gdy <math>R_1(x)</math> jest spełniona oraz <math>x\in L_2</math>, gdy <math>R_2(x)</math> jest nie spełniona.
Na podstawie konstrukcji wiemy, ¿e <math>x\in L_1</math>, gdy <math>R_1(x)</math> jest spe³niona oraz <math>x\in L_2</math>, gdy <math>R_2(x)</math> jest nie spe³niona.
zatem <math>x\in L_1 \cap L_2</math> gdy <math>R(x)\in</math>SAT-UNSAT.
zatem <math>x\in L_1 \cap L_2</math> gdy <math>R(x)\in</math>SAT-UNSAT.
}}
</div>}}</div>


Również wspomniany na początku problem EXACT TSP jest DP-zupełny.
Równie¿ wspomniany na pocz±tku problem EXACT TSP jest DP-zupe³ny.
Można rozważać także wiele innych wersji EXACT znanych problemów NP-zupełnych, które okazują się DP-zupełne.
Mo¿na rozwa¿aæ tak¿e wiele innych wersji EXACT znanych problemów NP-zupe³nych, które okazuj± siê DP-zupe³ne.


Klasa DP zawiera także problemy DP-zupełne innego rodzaju:
Klasa DP zawiera tak¿e problemy DP-zupe³ne innego rodzaju:


{{przyklad|[Uzupelnij]||
{{przyklad|[Uzupelnij]||
Problem CRITICAL SAT:<br>
Problem CRITICAL SAT:<br>
Wejście: formuła logiczna <math>\phi</math> jak dla SAT.<br>
Wej¶cie: formu³a logiczna <math>\phi</math> jak dla SAT.<br>
Wyjście: czy formuła <math>\phi</math> jest nie spełnialna, natomiast usunięcie dowolnej klauzuli sprawia, że jest spełnialna?
Wyj¶cie: czy formu³a <math>\phi</math> jest nie spe³nialna, natomiast usuniêcie dowolnej klauzuli sprawia, ¿e jest spe³nialna?
}}
}}


{{przyklad|[Uzupelnij]||
{{przyklad|[Uzupelnij]||
Problem CRITICAL HAMILTON PATH:<br>
Problem CRITICAL HAMILTON PATH:<br>
Wejście: graf nieskierowany <math>G</math><br>
Wej¶cie: graf nieskierowany <math>G</math><br>
Wyjście: czy <math>G</math> nie ma ścieżki Hamiltona, natomiast dodanie dowolnej krawędzi do <math>G</math> powoduje, że już ją posiada?
Wyj¶cie: czy <math>G</math> nie ma ¶cie¿ki Hamiltona, natomiast dodanie dowolnej krawêdzi do <math>G</math> powoduje, ¿e ju¿ j± posiada?
}}
}}


==Maszyny alternujące==
==Maszyny alternuj±ce==


W tym rozdziale przedstawimy ciekawe uogólnienie niedeterminizmu, zwane alternacją.
W tym rozdziale przedstawimy ciekawe uogólnienie niedeterminizmu, zwane alternacj±.
Przypomnijmy, że maszyna niedeterministyczna akceptuje słowo, gdy na którejkolwiek ze ścieżek
Przypomnijmy, ¿e maszyna niedeterministyczna akceptuje s³owo, gdy na którejkolwiek ze ¶cie¿ek
obliczeń trafi do stanu akceptującego.
obliczeñ trafi do stanu akceptuj±cego.


Maszyna alternująca ma więcej możliwości. Każdy z jej stanów jest oznaczony poprzez "AND" lub "OR",
Maszyna alternuj±ca ma wiêcej mo¿liwo¶ci. Ka¿dy z jej stanów jest oznaczony poprzez "AND" lub "OR",
które nazywamy odpowiednio stanami uniwersalnymi i egzystencjalnymi.
które nazywamy odpowiednio stanami uniwersalnymi i egzystencjalnymi.


Gdy maszyna jest w stanie typu "OR", to dokonuje akceptacji gdy dowolna ze ścieżek obliczeń wychodzących z niego akceptuje słowo.
Gdy maszyna jest w stanie typu "OR", to dokonuje akceptacji gdy dowolna ze ¶cie¿ek obliczeñ wychodz±cych z niego akceptuje s³owo.
Tak właśnie działają zawsze zwykłe maszyny niedeterministyczne.
Tak w³a¶nie dzia³aj± zawsze zwyk³e maszyny niedeterministyczne.


Stany typu "AND" są rozszerzają tą funkcjonalność. Maszyna dokonuje akceptacji będąc w takim stanie, gdy ''każda'' ze ścieżek obliczeń
Stany typu "AND" s± rozszerzaj± t± funkcjonalno¶æ. Maszyna dokonuje akceptacji bêd±c w takim stanie, gdy ''ka¿da'' ze ¶cie¿ek obliczeñ
wychodzących z tego stanu jest akceptująca.
wychodz±cych z tego stanu jest akceptuj±ca.


Miarę złożoności czasowej i pamięciowej maszyn alternujących definiujemy zupełnie tak jak dla maszyn niedeterministycznych, tzn.
Miarê z³o¿ono¶ci czasowej i pamiêciowej maszyn alternuj±cych definiujemy zupe³nie tak jak dla maszyn niedeterministycznych, tzn.
funkcja <math>f(n)</math> jest miarą złożoności czasowej, gdy każda ze ścieżek obliczeń ma długość ograniczoną przez <math>f(n)</math> oraz złożoność
funkcja <math>f(n)</math> jest miar± z³o¿ono¶ci czasowej, gdy ka¿da ze ¶cie¿ek obliczeñ ma d³ugo¶æ ograniczon± przez <math>f(n)</math> oraz z³o¿ono¶æ
pamięciową <math>f(n)</math> gdy na każdej ze ścieżek obliczeń maszyna zużywa co najwyżej <math>f(n)</math> pamięci.
pamiêciow± <math>f(n)</math> gdy na ka¿dej ze ¶cie¿ek obliczeñ maszyna zu¿ywa co najwy¿ej <math>f(n)</math> pamiêci.


{{definicja|[Uzupelnij]||
{{definicja|[Uzupelnij]||
Poprzez <math>\textsc{ATIME}(f(n))</math> oznaczamy zbiór języków <math>L</math> takich, że są akceptowane przez alternującą maszynę Turinga <math>M</math> o złożoności
Poprzez <math>\textsc{ATIME}(f(n))</math> oznaczamy zbiór jêzyków <math>L</math> takich, ¿e s± akceptowane przez alternuj±c± maszynê Turinga <math>M</math> o z³o¿ono¶ci
czasowej <math>f(n)</math>.
czasowej <math>f(n)</math>.
}}
}}


{{definicja|[Uzupelnij]||
{{definicja|[Uzupelnij]||
Poprzez <math>\textsc{ASPACE}(f(n))</math> oznaczamy zbiór języków <math>L</math> takich, że są akceptowane przez alternującą maszynę Turinga <math>M</math> o złożoności
Poprzez <math>\textsc{ASPACE}(f(n))</math> oznaczamy zbiór jêzyków <math>L</math> takich, ¿e s± akceptowane przez alternuj±c± maszynê Turinga <math>M</math> o z³o¿ono¶ci
pamięciowej <math>f(n)</math>.
pamiêciowej <math>f(n)</math>.
}}
}}


Wprowadzamy też skróty dla najpopularniejszych klas:
Wprowadzamy te¿ skróty dla najpopularniejszych klas:


* Klasa AP =  ATIME <math>(n^k) = \bigcup_{j>0} </math> ATIME <math>(n^j)</math>, to klasa tych języków, które mogą być akceptowane w alternującym czasie wielomianowym,
* Klasa AP =  ATIME <math>(n^k) = \bigcup_{j>0} </math> ATIME <math>(n^j)</math>, to klasa tych jêzyków, które mog± byæ akceptowane w alternuj±cym czasie wielomianowym,
* Klasa AL = ASPACE(log<math>n</math>), to klasa tych języków, które mogą być akceptowane w alternującej pamięci logarytmicznej,


Nietrudno się domyślić, że alternacja jest silniejsza niż niedeterminizm z definicji działania maszyn. Wiemy zatem, w szczególności, że
* Klasa AL = ASPACE(log<math>n</math>), to klasa tych jêzyków, które mog± byæ akceptowane w alternuj±cej pamiêci logarytmicznej,
<math>AP</math> zawiera w sobie <math>NP</math>. Poniższe ćwiczenie pokazuje, że o AP można powiedzieć więcej:
 
Nietrudno siê domy¶liæ, ¿e alternacja jest silniejsza ni¿ niedeterminizm z definicji dzia³ania maszyn. Wiemy zatem, w szczególno¶ci, ¿e
<math>AP</math> zawiera w sobie <math>NP</math>. Poni¿sze æwiczenie pokazuje, ¿e o AP mo¿na powiedzieæ wiêcej:


{{cwiczenie||
{{cwiczenie||
Pokaż, że AP zawiera w sobie klasę coNP.
Poka¿, ¿e AP zawiera w sobie klasê coNP.
}}
}}


{{wskazowka|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none">
Pokaż że problem coNP-zupełny TAUTOLOGY należy do AP.
Poka¿ ¿e problem coNP-zupe³ny TAUTOLOGY nale¿y do AP.
}}
</div>}}</div>


{{rozwiazanie||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none">
Na mocy wskazówki pokażemy, że TAUTOLOGY <math>\in</math> AP, a tym samym ponieważ AP jest zamknięta na redukcje, to cała klasa coNP zawiera się w AP.
Na mocy wskazówki poka¿emy, ¿e TAUTOLOGY <math>\in</math> AP, a tym samym poniewa¿ AP jest zamkniêta na redukcje, to ca³a klasa coNP zawiera siê w AP.


Maszyna dla TAUTOLOGY rozpoczyna działanie od stanu uniwersalnego. Następnie na każdej ze ścieżek obliczeń sprawdza inne wartościowanie.
Maszyna dla TAUTOLOGY rozpoczyna dzia³anie od stanu uniwersalnego. Nastêpnie na ka¿dej ze ¶cie¿ek obliczeñ sprawdza inne warto¶ciowanie.
Jeśli <math>\phi</math> jest spełniona na danym wartościowaniu, to obliczenie dochodzi do stanu akceptującego. W ten sposób ze względu
Je¶li <math>\phi</math> jest spe³niona na danym warto¶ciowaniu, to obliczenie dochodzi do stanu akceptuj±cego. W ten sposób ze wzglêdu
na swój tryb działania, maszyna zaakceptuje <math>\phi</math>, gdy jest ona spełniona dla każdego wartościowania, czyli, gdy jest tautologią logiczną.
na swój tryb dzia³ania, maszyna zaakceptuje <math>\phi</math>, gdy jest ona spe³niona dla ka¿dego warto¶ciowania, czyli, gdy jest tautologi± logiczn±.
}}
</div>}}</div>


To jednak nie wszystko co potrafi klasa AP. Znajdują się w niej języki, o których nie wiemy czy należą do NP lub coNP.
To jednak nie wszystko co potrafi klasa AP. Znajduj± siê w niej jêzyki, o których nie wiemy czy nale¿± do NP lub coNP.


{{definicja|[Uzupelnij]||
{{definicja|[Uzupelnij]||
Problem MIN-FORMULA:<br>
Problem MIN-FORMULA:<br>
Wejście: formuła logiczna <math>\phi</math> jak dla problemu SAT.<br>
Wej¶cie: formu³a logiczna <math>\phi</math> jak dla problemu SAT.<br>
Wyjście: czy <math>\phi</math> jest minimalna, tzn. czy żadna krótsza formuła nie jest jej równoważna?
Wyj¶cie: czy <math>\phi</math> jest minimalna, tzn. czy ¿adna krótsza formu³a nie jest jej równowa¿na?
}}
}}


{{cwiczenie||
{{cwiczenie||
Pokaż, że MIN-FORMULA należy do AP.
Poka¿, ¿e MIN-FORMULA nale¿y do AP.
}}
}}


{{wskazowka|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none">
Wykorzystaj dwa tryby alternacji.
Wykorzystaj dwa tryby alternacji.
}}
</div>}}</div>


{{rozwiazanie||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none">
W pierwszej części maszyna działa w trybie "AND". Zgadujemy formułę <math>\psi</math> krótszą niż <math>\phi</math>, a następnie
W pierwszej czê¶ci maszyna dzia³a w trybie "AND". Zgadujemy formu³ê <math>\psi</math> krótsz± ni¿ <math>\phi</math>, a nastêpnie
przestawiamy się na tryb "OR". Teraz zgadujemy wartościowanie <math>s</math>. Jeśli <math>\phi</math> i <math>\psi</math> są rozróżniane przez
przestawiamy siê na tryb "OR". Teraz zgadujemy warto¶ciowanie <math>s</math>. Je¶li <math>\phi</math> i <math>\psi</math> s± rozró¿niane przez
<math>s</math>, tzn. jedna z nich jest spełniona, a druga nie, to akceptujemy formułę <math>\phi</math>.
<math>s</math>, tzn. jedna z nich jest spe³niona, a druga nie, to akceptujemy formu³ê <math>\phi</math>.


Załóżmy nie wprost, że formuła nie jest minimalna, a mimo to zostaje zaakceptowana.
Za³ó¿my nie wprost, ¿e formu³a nie jest minimalna, a mimo to zostaje zaakceptowana.
Aby tak się stało na każdej ze ścieżek z pierwszego poziomu alternacji uniwersalnej maszyna musi zaakceptować.
Aby tak siê sta³o na ka¿dej ze ¶cie¿ek z pierwszego poziomu alternacji uniwersalnej maszyna musi zaakceptowaæ.
Jeśli jednak formuła nie jest minimalna, to istnieje krótsza od niej formuła <math>\psi</math>, które jest jej równoważna. Na ścieżce obliczeń
Je¶li jednak formu³a nie jest minimalna, to istnieje krótsza od niej formu³a <math>\psi</math>, które jest jej równowa¿na. Na ¶cie¿ce obliczeñ
rozważającej <math>\psi</math> maszyna w drugim poziomie alternacji musi znaleźć wartościowanie, które rozróżnia <math>\phi</math> i <math>\psi</math> co jest
rozwa¿aj±cej <math>\psi</math> maszyna w drugim poziomie alternacji musi znale¼æ warto¶ciowanie, które rozró¿nia <math>\phi</math> i <math>\psi</math> co jest
niemożliwe, stąd uzyskujemy sprzeczność.
niemo¿liwe, st±d uzyskujemy sprzeczno¶æ.
}}
</div>}}</div>


Teraz przedstawimy kilka relacji pomiędzy klasami obliczeń alternujących:
Teraz przedstawimy kilka relacji pomiêdzy klasami obliczeñ alternuj±cych:


{{twierdzenie|[Uzupelnij]||
{{twierdzenie|[Uzupelnij]||


Następujące relacje są prawdziwe:
Nastêpuj±ce relacje s± prawdziwe:
 
# Je¶li <math>f(n)\geqslant n</math> to  ATIME <math>(f(n)) \subseteq </math> SPACE <math>(f(n))</math>,
 
# Je¶li <math>f(n)\geqslant n</math> to  SPACE <math>(f(n)) \subseteq </math> ATIME <math>(f^2(n))</math>,


# Jeśli <math>f(n)\geqslant n</math> to  ATIME <math>(f(n)) \subseteq </math> SPACE <math>(f(n))</math>,
# Je¶li <math>f(n)\geqslant </math> log <math>n</math> to  ASPACE <math>(f(n)) \subseteq </math> TIME <math>(c^{f(n)})</math>.
# Jeśli <math>f(n)\geqslant n</math> to  SPACE <math>(f(n)) \subseteq </math> ATIME <math>(f^2(n))</math>,
 
# Jeśli <math>f(n)\geqslant </math> log <math>n</math> to  ASPACE <math>(f(n)) \subseteq </math> TIME <math>(c^{f(n)})</math>.
# Je¶li <math>f(n)\geqslant </math> log <math>n</math> to  ASPACE <math>(f(n)) \supseteq </math> TIME <math>(c^{f(n)})</math>.
# Jeśli <math>f(n)\geqslant </math> log <math>n</math> to  ASPACE <math>(f(n)) \supseteq </math> TIME <math>(c^{f(n)})</math>.


}}
}}


{{dowod|[Uzupelnij]||
{{dowod|[Uzupelnij]||
Dowód własności od 1 do 3 jest przedmiotem ćwiczenia końcowego. Własność 4 wymaga trochę więcej pracy.
Dowód w³asno¶ci od 1 do 3 jest przedmiotem æwiczenia koñcowego. W³asno¶æ 4 wymaga trochê wiêcej pracy.
Zauważmy, że musimy symulować maszynę działającą w czasie wykładniczym
Zauwa¿my, ¿e musimy symulowaæ maszynê dzia³aj±c± w czasie wyk³adniczym
od dostępnej nam pamięci! Nie mamy zatem miejsca na potencjalną ilość pamięci, która może być potrzebna.
od dostêpnej nam pamiêci! Nie mamy zatem miejsca na potencjaln± ilo¶æ pamiêci, która mo¿e byæ potrzebna.
Okazuje się jednak, że można sobie z tym poradzić:
Okazuje siê jednak, ¿e mo¿na sobie z tym poradziæ:


Weźmy dowolną maszynę deterministyczną <math>M</math> działającą w czasie <math>c^{f(n)}</math>. Będziemy symulować jej obliczenia od końca.
We¼my dowoln± maszynê deterministyczn± <math>M</math> dzia³aj±c± w czasie <math>c^{f(n)}</math>. Bêdziemy symulowaæ jej obliczenia od koñca.
Najpierw ustalamy, bez straty ogólności, że jest tylko jedna końcowa konfiguracja akceptująca, np. z całkowicie pustą taśmą
Najpierw ustalamy, bez straty ogólno¶ci, ¿e jest tylko jedna koñcowa konfiguracja akceptuj±ca, np. z ca³kowicie pust± ta¶m±
, głowicą w komórce o numerze 1 i stanie <math>q_{acc}</math>.
, g³owic± w komórce o numerze 1 i stanie <math>q_{acc}</math>.


Możemy przedstawić całe obliczenie w formie następującej tabelki przedstawiającej w rzędach kolejne zawartości
Mo¿emy przedstawiæ ca³e obliczenie w formie nastêpuj±cej tabelki przedstawiaj±cej w rzêdach kolejne zawarto¶ci
taśmy, a w kolumnach czas. Dla uproszczenia przyjmijmy, że taśma jest jedna, i że pozycję głowicy notujemy specjalnym zapisem
ta¶my, a w kolumnach czas. Dla uproszczenia przyjmijmy, ¿e ta¶ma jest jedna, i ¿e pozycjê g³owicy notujemy specjalnym zapisem
w tym miejscu pamięci, które ona odczytuje (podobnie notujemy stan).
w tym miejscu pamiêci, które ona odczytuje (podobnie notujemy stan).
W ten sposób zawartość komórki <math>d</math> zależy tylko od zawartości komórek <math>a</math>, <math>b</math> i <math>c</math>:
W ten sposób zawarto¶æ komórki <math>d</math> zale¿y tylko od zawarto¶ci komórek <math>a</math>, <math>b</math> i <math>c</math>:


{1cm}
{1cm}


[width=10cm]{ZO-13-2-rys.jpg}<br>
[width=10cm]{ZO-13-2-rys.jpg}<br>
Zapis przebiegu obliczeń
Zapis przebiegu obliczeñ


{1cm}
{1cm}


Teraz rozpoczynamy od dolnej części tabeli, której zawartość znamy i chcemy sprawdzić, czy obliczenie rozpoczęło się
Teraz rozpoczynamy od dolnej czê¶ci tabeli, której zawarto¶æ znamy i chcemy sprawdziæ, czy obliczenie rozpoczê³o siê
od pierwszego wiersza, który jest wejściem i którego zawartość też znamy.
od pierwszego wiersza, który jest wej¶ciem i którego zawarto¶æ te¿ znamy.


Jeśli chcemy zweryfikować wartość komórki <math>d</math>, to w trybie "OR" zgadujemy zawartość komórek <math>a</math>, <math>b</math> i <math>c</math>. Następnie w trybie
Je¶li chcemy zweryfikowaæ warto¶æ komórki <math>d</math>, to w trybie "OR" zgadujemy zawarto¶æ komórek <math>a</math>, <math>b</math> i <math>c</math>. Nastêpnie w trybie
"AND" weryfikujemy ich poprawność i zgodność przejścia od <math>a</math>, <math>b</math>, <math>c</math> do <math>d</math>.
"AND" weryfikujemy ich poprawno¶æ i zgodno¶æ przej¶cia od <math>a</math>, <math>b</math>, <math>c</math> do <math>d</math>.


Ile pamięci jest nam potrzebne? Musimy pamiętać tylko wskaźniki do miejsc w wielkiej tabeli przedstawionej na rysunku,
Ile pamiêci jest nam potrzebne? Musimy pamiêtaæ tylko wska¼niki do miejsc w wielkiej tabeli przedstawionej na rysunku,
które sa rozmiaru  log <math>(c^{f(n)})</math>, co jest rzędu <math>f(n)</math>.
które sa rozmiaru  log <math>(c^{f(n)})</math>, co jest rzêdu <math>f(n)</math>.
}}
}}


Dzięki wymienionym relacjom pomiędzy klasami alternującymi możemy udowodnić kilka dokładnych równości pomiędzy klasami, a to rzadka
Dziêki wymienionym relacjom pomiêdzy klasami alternuj±cymi mo¿emy udowodniæ kilka dok³adnych równo¶ci pomiêdzy klasami, a to rzadka
rzecz w teorii złożoności. Wiemy zatem, że:
rzecz w teorii z³o¿ono¶ci. Wiemy zatem, ¿e:


* AL=P,
* AL=P,
* APSPACE = EXP,
* APSPACE = EXP,
* AP=PSPACE.
* AP=PSPACE.


==Hierarchia wielomianowa==
==Hierarchia wielomianowa==


W tej części zdefiniujemy całą hierarchię klas ponad znanymi nam już P i NP, która stanowi pewne uogólnienie problematyki spotkanej w klasie DP.
W tej czê¶ci zdefiniujemy ca³± hierarchiê klas ponad znanymi nam ju¿ P i NP, która stanowi pewne uogólnienie problematyki spotkanej w klasie DP.


W poprzednich rozdziałach zdefiniowaliśmy pojęcie maszyny z wyrocznią na język <math>L</math> oznaczanej przez <math>M^L</math>. Przypomnijmy, że jest to zwykła maszyna <math>M</math>
W poprzednich rozdzia³ach zdefiniowali¶my pojêcie maszyny z wyroczni± na jêzyk <math>L</math> oznaczanej przez <math>M^L</math>. Przypomnijmy, ¿e jest to zwyk³a maszyna <math>M</math>
z dodatkową możliwością zadania pytania postaci "czy <math>x\in L</math>?" które kosztuje jedną jednostkę czasu. Rozszerzenie tego pojęcia na klasy jest
z dodatkow± mo¿liwo¶ci± zadania pytania postaci "czy <math>x\in L</math>?" które kosztuje jedn± jednostkê czasu. Rozszerzenie tego pojêcia na klasy jest
naturalne. Poprzez <math>P^{NP}</math> oznaczamy zbiór tych języków, które mogą być rozstrzygane przez maszyny z klasy <math>P</math> z wyrocznią na dowolny język z klasy <math>NP</math>.
naturalne. Poprzez <math>P^{NP}</math> oznaczamy zbiór tych jêzyków, które mog± byæ rozstrzygane przez maszyny z klasy <math>P</math> z wyroczni± na dowolny jêzyk z klasy <math>NP</math>.


Ta klasa okazuje się być mocniejsza od DP, bowiem w DP mogliśmy zadań pytanie tylko raz (dotyczące coNP, ale w sensie wyroczni działa to jak pytanie do NP),
Ta klasa okazuje siê byæ mocniejsza od DP, bowiem w DP mogli¶my zadañ pytanie tylko raz (dotycz±ce coNP, ale w sensie wyroczni dzia³a to jak pytanie do NP),
a tutaj dowolną liczbę razy i to na dodatek pytań adaptywnych, tzn.
a tutaj dowoln± liczbê razy i to na dodatek pytañ adaptywnych, tzn.
takich, które mogą zależeć od wyników odpowiedzi na poprzednie z nich. Kolejną interesującą klasą jest <math>NP^{NP}</math>. Wszystkie te klasy
takich, które mog± zale¿eæ od wyników odpowiedzi na poprzednie z nich. Kolejn± interesuj±c± klas± jest <math>NP^{NP}</math>. Wszystkie te klasy
dają nam coraz większe możliwości, lecz oczywiście nie wiadomo, czy są to ściśle większe klasy, choć panuje takie przekonanie:
daj± nam coraz wiêksze mo¿liwo¶ci, lecz oczywi¶cie nie wiadomo, czy s± to ¶ci¶le wiêksze klasy, choæ panuje takie przekonanie:


{1cm}
{1cm}
Linia 457: Linia 466:
{1cm}
{1cm}


Postępując w ten sposób Meyer i Stockmeyer w latach 70 zdefiniowali całą hierarchię klas:
Postêpuj±c w ten sposób Meyer i Stockmeyer w latach 70 zdefiniowali ca³± hierarchiê klas:


{{definicja|[Uzupelnij]||
{{definicja|[Uzupelnij]||
Hierarchia wielomianowa, to ciąg klas indeksowany poprzez <math>i</math>:<br>
Hierarchia wielomianowa, to ci±g klas indeksowany poprzez <math>i</math>:<br>


* <math>\sum_0 P = \prod_0 P = \Delta_0 P = P</math>
* <math>\sum_0 P = \prod_0 P = \Delta_0 P = P</math>
* <math>\Delta_{i+1} P = P^{\sum_i P},</math>  dla  <math>i>0</math>,
* <math>\Delta_{i+1} P = P^{\sum_i P},</math>  dla  <math>i>0</math>,
* <math>\sum_{i+1} P = NP^{\sum_i P},</math>  dla  <math>i>0</math>,
* <math>\sum_{i+1} P = NP^{\sum_i P},</math>  dla  <math>i>0</math>,
* <math>\prod_{i+1} P = coNP^{\sum_i P},</math>  dla  <math>i>0</math>.
* <math>\prod_{i+1} P = coNP^{\sum_i P},</math>  dla  <math>i>0</math>.


Dodatkowo poprzez <math>PH</math> oznaczamy sumę wszystkich tych klas, czyli:<br>
Dodatkowo poprzez <math>PH</math> oznaczamy sumê wszystkich tych klas, czyli:<br>
<math>PH=\bigcup_{i\geqslant 0} \sum_i P</math>.
<math>PH=\bigcup_{i\geqslant 0} \sum_i P</math>.
}}
}}


Ponieważ na poziomie zerowym wszystkie elementy hierarchii to P, więc na poziomie pierwszym,
Poniewa¿ na poziomie zerowym wszystkie elementy hierarchii to P, wiêc na poziomie pierwszym,
ponieważ taka wyrocznia nic nie daje, otrzymujemy <math>\Delta_1 P = P, \sum_1 P = NP, \prod_1 P = coNP</math>.
poniewa¿ taka wyrocznia nic nie daje, otrzymujemy <math>\Delta_1 P = P, \sum_1 P = NP, \prod_1 P = coNP</math>.
Drugi poziom, to klasy<math>\Delta_2 P = P^{NP}, \sum_2 P = NP^{NP}, \prod_2 P = coNP^{NP}</math>.
Drugi poziom, to klasy<math>\Delta_2 P = P^{NP}, \sum_2 P = NP^{NP}, \prod_2 P = coNP^{NP}</math>.
Warto zwrócić uwagę, że <math>\prod_i P</math> jest dopełnieniem <math>\sum_i P</math> na każdym poziomie wprost z definicji.
Warto zwróciæ uwagê, ¿e <math>\prod_i P</math> jest dope³nieniem <math>\sum_i P</math> na ka¿dym poziomie wprost z definicji.
Zawieranie się poszczególnych elementów na jednym poziomie obrazuje poniższy rysunek:
Zawieranie siê poszczególnych elementów na jednym poziomie obrazuje poni¿szy rysunek:


{1cm}
{1cm}
Linia 484: Linia 496:
{1cm}
{1cm}


Do tej pory często odwoływaliśmy się do odpowiedniości pomiędzy klasą NP a szczególnymi relacjami wielomianowo
Do tej pory czêsto odwo³ywali¶my siê do odpowiednio¶ci pomiêdzy klas± NP a szczególnymi relacjami wielomianowo
zrównoważonymi i rozstrzygalnymi. Przedstawimy teraz zgrabną charakteryzację klas z hierarchii wielomianowej przy pomocy
zrównowa¿onymi i rozstrzygalnymi. Przedstawimy teraz zgrabn± charakteryzacjê klas z hierarchii wielomianowej przy pomocy
podobnego kryterium:
podobnego kryterium:


{{twierdzenie|[Uzupelnij]||
{{twierdzenie|[Uzupelnij]||
Niech <math>L</math> będzie językiem, <math>i>0</math>. Język <math>L</math> należy do <math>\sum_i P</math> wtedy i tylko wtedy, gdy istnieje wielomianowo zrównoważona i rozstrzygalna
Niech <math>L</math> bêdzie jêzykiem, <math>i>0</math>. Jêzyk <math>L</math> nale¿y do <math>\sum_i P</math> wtedy i tylko wtedy, gdy istnieje wielomianowo zrównowa¿ona i rozstrzygalna
relacja <math>R</math> (<math>i+1</math>-argumentowa), taka, że <math>x \in L</math> dokładnie wtedy, gdy
relacja <math>R</math> (<math>i+1</math>-argumentowa), taka, ¿e <math>x \in L</math> dok³adnie wtedy, gdy
<math>\exists{y_1}\forall{y_2}\exists{y_3}\ldots Q{y_i}</math> takie, że <math>R(x,y_1,\ldots,y_i)</math> jest spełnione (<math>i</math>-ty kwantyfikator jest uniwersalny, gdy <math>i</math> jest
<math>\exists{y_1}\forall{y_2}\exists{y_3}\ldots Q{y_i}</math> takie, ¿e <math>R(x,y_1,\ldots,y_i)</math> jest spe³nione (<math>i</math>-ty kwantyfikator jest uniwersalny, gdy <math>i</math> jest
parzyste, natomiast egzystencjalny, gdy <math>i</math> jest nieparzyste).
parzyste, natomiast egzystencjalny, gdy <math>i</math> jest nieparzyste).
}}
}}


Hierarchia wielomianowa jest strukturą dosyć wrażliwą na kolapsy, tzn. równości klas na pewnym poziomie. Okazuje się, że wtedy przenoszą się
Hierarchia wielomianowa jest struktur± dosyæ wra¿liw± na kolapsy, tzn. równo¶ci klas na pewnym poziomie. Okazuje siê, ¿e wtedy przenosz± siê
one automatycznie w górę:
one automatycznie w górê:


{{cwiczenie||
{{cwiczenie||
Pokaż, że jeżeli dla pewnego <math>i</math> zachodzi <math>\sum_i P = \prod_i P</math> to dla każdego <math>j>i</math> zachodzi <math>\sum_j P = \prod_j P = \Delta_j P = \sum_i P</math>.
Poka¿, ¿e je¿eli dla pewnego <math>i</math> zachodzi <math>\sum_i P = \prod_i P</math> to dla ka¿dego <math>j>i</math> zachodzi <math>\sum_j P = \prod_j P = \Delta_j P = \sum_i P</math>.
}}
}}


{{wskazowka|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none">
Pokaż, że <math>\sum_{i+1} P = \sum P</math>.
Poka¿, ¿e <math>\sum_{i+1} P = \sum P</math>.
}}
</div>}}</div>


{{rozwiazanie||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none">
Pokażemy równość podaną we wskazówce z założenia <math>\sum_i P = \prod_i P</math>. Weźmy dowolny <math>L\in\sum_{i+1} P</math>. Z poprzedniego twierdzenia
Poka¿emy równo¶æ podan± we wskazówce z za³o¿enia <math>\sum_i P = \prod_i P</math>. We¼my dowolny <math>L\in\sum_{i+1} P</math>. Z poprzedniego twierdzenia
charakteryzującego wiemy, że istnieje relacja <math>i+1</math>-argumentowa <math>R_L</math> dla <math>L</math>. Weźmy rzut relacji <math>R_L</math>, w którym pomijamy współrzędną <math>y_1</math>.
charakteryzuj±cego wiemy, ¿e istnieje relacja <math>i+1</math>-argumentowa <math>R_L</math> dla <math>L</math>. We¼my rzut relacji <math>R_L</math>, w którym pomijamy wspó³rzêdn± <math>y_1</math>.
Jest to relacja odpowiadająca pewnemu językowi <math>L'</math> z <math>\prod_i P</math> (otrzymujemy to dzięki zastosowaniu negacji i dopełnienia języka dla poprzedniego twierdzenia). W definicji tym razem jako pierwszy występuje
Jest to relacja odpowiadaj±ca pewnemu jêzykowi <math>L'</math> z <math>\prod_i P</math> (otrzymujemy to dziêki zastosowaniu negacji i dope³nienia jêzyka dla poprzedniego twierdzenia). W definicji tym razem jako pierwszy wystêpuje
kwantyfikator uniwersalny.
kwantyfikator uniwersalny.


Dzięki równości klas istnieje dla języka <math>L'</math> <math>i</math>-argumentowa relacja <math>R_{L'}</math>, definiująca go przy użyciu kwantyfikatora
Dziêki równo¶ci klas istnieje dla jêzyka <math>L'</math> <math>i</math>-argumentowa relacja <math>R_{L'}</math>, definiuj±ca go przy u¿yciu kwantyfikatora
egzystencjalnego na początku. Dzięki tej zmianie, możemy teraz zmienić <math>R_{L'}</math> tak, aby
egzystencjalnego na pocz±tku. Dziêki tej zmianie, mo¿emy teraz zmieniæ <math>R_{L'}</math> tak, aby
uwzględnić usuniętą wcześniej współrzędną współrzędną <math>y_1</math>, bez dodawania nowego kwantyfikatora, gdyż teraz jako pierwszy występuje kwantyfikator
uwzglêdniæ usuniêt± wcze¶niej wspó³rzêdn± wspó³rzêdn± <math>y_1</math>, bez dodawania nowego kwantyfikatora, gdy¿ teraz jako pierwszy wystêpuje kwantyfikator
egzystencjalny, co sprawia, że <math>L\in\sum_{i} P</math>.
egzystencjalny, co sprawia, ¿e <math>L\in\sum_{i} P</math>.
}}
</div>}}</div>


Zachodzi również podobny fakt. Otóż, jeśli P=NP (albo tylko NP=coNP), to hierarchia kolapsuje już na pierwszym poziomie.
Zachodzi równie¿ podobny fakt. Otó¿, je¶li P=NP (albo tylko NP=coNP), to hierarchia kolapsuje ju¿ na pierwszym poziomie.


Można by się zastanowić, czy kolejne poziomy hierarchii wielomianowej są interesujące z punku widzenia problemów, które pozwalają one rozwiązać.
Mo¿na by siê zastanowiæ, czy kolejne poziomy hierarchii wielomianowej s± interesuj±ce z punku widzenia problemów, które pozwalaj± one rozwi±zaæ.
Okazuje się, że na każdym poziomie hierarchii posiada ona problemy zupełne:
Okazuje siê, ¿e na ka¿dym poziomie hierarchii posiada ona problemy zupe³ne:


{{definicja|[Uzupelnij]||
{{definicja|[Uzupelnij]||
Problem  QSAT <math>_i</math>:<br>
Problem  QSAT <math>_i</math>:<br>
Wejście: formuła logiczna <math>\phi</math> jak dla problemu SAT poprzedzona <math>i</math> naprzemiennymi grupami kwantyfikatorów egzystencjalnych i uniwersalnych:
Wej¶cie: formu³a logiczna <math>\phi</math> jak dla problemu SAT poprzedzona <math>i</math> naprzemiennymi grupami kwantyfikatorów egzystencjalnych i uniwersalnych:
<math>\Phi=\exists{x_1}\forall{x_2}\exists{x_3}\ldots Q{x_i}\phi</math>.<br>
<math>\Phi=\exists{x_1}\forall{x_2}\exists{x_3}\ldots Q{x_i}\phi</math>.<br>
Wyjście: czy <math>\Phi</math> jest prawdziwa?
Wyj¶cie: czy <math>\Phi</math> jest prawdziwa?
}}
}}


{{twierdzenie|[Uzupelnij]||
{{twierdzenie|[Uzupelnij]||
Problem <math>QSAT_i</math> jest <math>\sum_i P</math>-zupełny dla <math>i>0</math>.
Problem <math>QSAT_i</math> jest <math>\sum_i P</math>-zupe³ny dla <math>i>0</math>.
}}
}}


Jednak pytanie czy istnieje problem PH-zupełny (czyli zupełny dla całej hierarchii) jest otwarte i panuje przekonanie, że tak nie jest, gdyż:
Jednak pytanie czy istnieje problem PH-zupe³ny (czyli zupe³ny dla ca³ej hierarchii) jest otwarte i panuje przekonanie, ¿e tak nie jest, gdy¿:


{{cwiczenie||
{{cwiczenie||
Pokaż, że jeśli istnieje problem PH-zupełny, to hierarchia zapada się na pewnym poziomie.
Poka¿, ¿e je¶li istnieje problem PH-zupe³ny, to hierarchia zapada siê na pewnym poziomie.
}}
}}


{{wskazowka|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none">
Zauważ, że problem zupełny musi należeć do konkretnego poziomu.
Zauwa¿, ¿e problem zupe³ny musi nale¿eæ do konkretnego poziomu.
}}
</div>}}</div>


{{rozwiazanie||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none">
Jeśli <math>L</math> jest zupełny dla PH, to <math>L</math> należy do <math>\sum_i P</math> dla pewnego <math>i</math>. Wtedy jednak dowolny język <math>L'</math> z poziomu <math>\sum_{i+1} P</math>
Je¶li <math>L</math> jest zupe³ny dla PH, to <math>L</math> nale¿y do <math>\sum_i P</math> dla pewnego <math>i</math>. Wtedy jednak dowolny jêzyk <math>L'</math> z poziomu <math>\sum_{i+1} P</math>
redukuje się do <math>L</math> w czasie wielomianowym. Ponieważ poziomy hierarchii są zamknięte na redukcje, stąd <math>L'\in \sum_i P</math>, a w konsekwencji
redukuje siê do <math>L</math> w czasie wielomianowym. Poniewa¿ poziomy hierarchii s± zamkniête na redukcje, st±d <math>L'\in \sum_i P</math>, a w konsekwencji
<math>\sum_{i+1} P=\sum_i P</math>.
<math>\sum_{i+1} P=\sum_i P</math>.
}}
</div>}}</div>


Jak silna jest cała hierarchia? Można łatwo zauważyć, że zawiera się ona w znanej już nam klasie PSPACE, ze względu na fakt, że można
Jak silna jest ca³a hierarchia? Mo¿na ³atwo zauwa¿yæ, ¿e zawiera siê ona w znanej ju¿ nam klasie PSPACE, ze wzglêdu na fakt, ¿e mo¿na
łatwo rozstrzygać w wielomianowej pamięci relacje, charakteryzujące problemy z PH, które opisywaliśmy wcześniej.
³atwo rozstrzygaæ w wielomianowej pamiêci relacje, charakteryzuj±ce problemy z PH, które opisywali¶my wcze¶niej.


Jak nietrudno się domyślić pytanie, czy PH=PSPACE jest otwarte. Bardzo interesujące jest jednak, że gdyby równość zachodziła, to
Jak nietrudno siê domy¶liæ pytanie, czy PH=PSPACE jest otwarte. Bardzo interesuj±ce jest jednak, ¿e gdyby równo¶æ zachodzi³a, to
ponieważ PSPACE zawiera problemy zupełne, to PH również by je zawierała, stąd zapadła by się na pewnym skończonym poziomie. Stąd przekonanie,
poniewa¿ PSPACE zawiera problemy zupe³ne, to PH równie¿ by je zawiera³a, st±d zapad³a by siê na pewnym skoñczonym poziomie. St±d przekonanie,
że PH zawiera się silnie w PSPACE.
¿e PH zawiera siê silnie w PSPACE.


Na koniec ciekawy rezultat autorstwa Seinosuke Tody (laureata
Na koniec ciekawy rezultat autorstwa Seinosuke Tody (laureata
nagrody Gödel'a z roku 1998) związany z klasą PH. Pokazał on, że
nagrody Gödel'a z roku 1998) zwi±zany z klas± PH. Pokaza³ on, ¿e
<math>PH\subseteq P^{PP}</math>, czyli wyrocznia na klasę <math>PP</math> jest
<math>PH\subseteq P^{PP}</math>, czyli wyrocznia na klasê <math>PP</math> jest
niesamowicie silna i pozwala pochłonąć tak misternie zbudowaną
niesamowicie silna i pozwala poch³on±æ tak misternie zbudowan±
piramidę coraz silniejszych klas.
piramidê coraz silniejszych klas.


==Ćwiczenia dodatkowe==
==Æwiczenia dodatkowe==


{{cwiczenie||
{{cwiczenie||
Pokaż, że problem TAUTOLOGY jest coNP-zupełny.
Poka¿, ¿e problem TAUTOLOGY jest coNP-zupe³ny.
}}
}}


{{wskazowka|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none">
Skorzystaj z faktu, że SAT jest NP-zupełny.
Skorzystaj z faktu, ¿e SAT jest NP-zupe³ny.
}}
</div>}}</div>


{{rozwiazanie||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none">
TAUTOLOGY należy do coNP. Weźmy dowolny inny problem <math>L</math> z coNP. Wiemy, że <math>\overline{L}</math> należy do NP, więc
TAUTOLOGY nale¿y do coNP. We¼my dowolny inny problem <math>L</math> z coNP. Wiemy, ¿e <math>\overline{L}</math> nale¿y do NP, wiêc
jest redukowalny do SAT - problemu NP-zupełnego, poprzez redukcję, którą oznaczymy jako <math>R</math>. Z definicji redukcji
jest redukowalny do SAT - problemu NP-zupe³nego, poprzez redukcjê, któr± oznaczymy jako <math>R</math>. Z definicji redukcji
otrzymujemy, że <math>x\in \overline{L}</math> wtedy i tylko wtedy, gdy <math>R(x)</math> jest spełnialna. Po zastosowaniu negacji mamy
otrzymujemy, ¿e <math>x\in \overline{L}</math> wtedy i tylko wtedy, gdy <math>R(x)</math> jest spe³nialna. Po zastosowaniu negacji mamy
, że <math>x\in L</math> wtedy i tylko wtedy, gdy <math>R(x)</math> jest nie spełnialna, tzn. <math>\neg R(x)</math> jest tautologią. Sprowadziliśmy zatem
, ¿e <math>x\in L</math> wtedy i tylko wtedy, gdy <math>R(x)</math> jest nie spe³nialna, tzn. <math>\neg R(x)</math> jest tautologi±. Sprowadzili¶my zatem
problem przynależności do dowolnego języka <math>L</math> z coNP do sprawdzania czy pewna formuła jest tautologią, co dowodzi
problem przynale¿no¶ci do dowolnego jêzyka <math>L</math> z coNP do sprawdzania czy pewna formu³a jest tautologi±, co dowodzi
coNP-zupełności problemu TAUTOLOGY.
coNP-zupe³no¶ci problemu TAUTOLOGY.
}}
</div>}}</div>


{{cwiczenie||
{{cwiczenie||
Udowodnij własności od 1 do 3 z twierdzenia [[##tw:arel|Uzupelnic tw:arel|]].
Udowodnij w³asno¶ci od 1 do 3 z twierdzenia [[##tw:arel|Uzupelnic tw:arel|]].
 
# Je¶li <math>f(n)\geqslant n</math> to  ATIME <math>(f(n)) \subseteq </math> SPACE <math>(f(n))</math>,
 
# Je¶li <math>f(n)\geqslant n</math> to  SPACE <math>(f(n)) \subseteq </math> ATIME <math>(f^2(n))</math>,


# Jeśli <math>f(n)\geqslant n</math> to  ATIME <math>(f(n)) \subseteq </math> SPACE <math>(f(n))</math>,
# Je¶li <math>f(n)\geqslant </math> log <math>n</math> to  ASPACE <math>(f(n)) \subseteq </math> TIME <math>(c^{f(n)})</math>.
# Jeśli <math>f(n)\geqslant n</math> to  SPACE <math>(f(n)) \subseteq </math> ATIME <math>(f^2(n))</math>,
# Jeśli <math>f(n)\geqslant </math> log <math>n</math> to  ASPACE <math>(f(n)) \subseteq </math> TIME <math>(c^{f(n)})</math>.


}}
}}


{{wskazowka|||<br>
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none"><br>
Ad. 1 i 3: zasymuluj maszynę alternującą przy pomocy zwykłej.<br>
Ad. 1 i 3: zasymuluj maszynê alternuj±c± przy pomocy zwyk³ej.<br>
Ad. 2: skorzystaj z idei zaczerpniętej z twierdzenia Savitcha.<br>
Ad. 2: skorzystaj z idei zaczerpniêtej z twierdzenia Savitcha.<br>
}}
</div>}}</div>


{{rozwiazanie||<br>
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none"><br>
Ad. 1:<br>
Ad. 1:<br>
Weźmy dowolny język <math>L\in</math> ATIME <math>(f(n))</math> akceptowany przez alternującą maszynę Turinga <math>M</math>.
We¼my dowolny jêzyk <math>L\in</math> ATIME <math>(f(n))</math> akceptowany przez alternuj±c± maszynê Turinga <math>M</math>.
Dokonamy symulacji przy pomocy deterministycznej maszyny w pamięci <math>f(n)</math>. Wykonujemy algorytm
Dokonamy symulacji przy pomocy deterministycznej maszyny w pamiêci <math>f(n)</math>. Wykonujemy algorytm
rekurencyjnego przeglądania grafu konfiguracji w głąb. W momencie powrotu z rekurencji z ostatniego potomka
rekurencyjnego przegl±dania grafu konfiguracji w g³±b. W momencie powrotu z rekurencji z ostatniego potomka
danego wierzchołka decydujemy na podstawie typu "OR" lub "AND" i akceptacji potomków o tym czy dana konfiguracja
danego wierzcho³ka decydujemy na podstawie typu "OR" lub "AND" i akceptacji potomków o tym czy dana konfiguracja
jest akceptująca. Głębokość rekurencji to czas obliczeń maszyny <math>M</math>, czyli <math>f(n)</math>. Na każdy poziom rekurencji
jest akceptuj±ca. G³êboko¶æ rekurencji to czas obliczeñ maszyny <math>M</math>, czyli <math>f(n)</math>. Na ka¿dy poziom rekurencji
potrzeba nam jednak <math>f(n)</math>, aby zapamiętać konfigurację, czyli łącznie <math>f^2(n)</math>.
potrzeba nam jednak <math>f(n)</math>, aby zapamiêtaæ konfiguracjê, czyli ³±cznie <math>f^2(n)</math>.


Możemy jednak zaoszczędzić na pamięci pamiętając tylko który z niedeterministycznych wyborów dokonała <math>M</math> na danym poziomie
Mo¿emy jednak zaoszczêdziæ na pamiêci pamiêtaj±c tylko który z niedeterministycznych wyborów dokona³a <math>M</math> na danym poziomie
rekurencji. Teraz aby obliczyć pełną konfigurację, będziemy musieli rozpocząć za każdym razem obliczenia od początku
rekurencji. Teraz aby obliczyæ pe³n± konfiguracjê, bêdziemy musieli rozpocz±æ za ka¿dym razem obliczenia od pocz±tku
dokonując stosownych wyborów. Taka operacja może być jednak wykonana w pamięci <math>f(n)</math>, stąd cała symulacja
dokonuj±c stosownych wyborów. Taka operacja mo¿e byæ jednak wykonana w pamiêci <math>f(n)</math>, st±d ca³a symulacja
potrzebuje <math>f(n)</math> pamięci, a więc <math>L\in</math> SPACE <math>(f(n))</math>.
potrzebuje <math>f(n)</math> pamiêci, a wiêc <math>L\in</math> SPACE <math>(f(n))</math>.


Ad. 2:<br>
Ad. 2:<br>
Tym razem mamy do dyspozycji maszynę działającą w pamięci <math>f(n)</math> i chcemy ją zasymulować przy pomocy maszyny alternującej
Tym razem mamy do dyspozycji maszynê dzia³aj±c± w pamiêci <math>f(n)</math> i chcemy j± zasymulowaæ przy pomocy maszyny alternuj±cej
w czasie <math>f^2(n)</math>.  Jak w twierdzeniu Savitcha odwołamy się do grafu konfiguracji maszyny rozmiaru <math>c^{f(n)}</math> i będziemy się starali
w czasie <math>f^2(n)</math>.  Jak w twierdzeniu Savitcha odwo³amy siê do grafu konfiguracji maszyny rozmiaru <math>c^{f(n)}</math> i bêdziemy siê starali
odpowiedzieć na pytanie, czy istnieje ścieżka od konfiguracji początkowej do końcowej.
odpowiedzieæ na pytanie, czy istnieje ¶cie¿ka od konfiguracji pocz±tkowej do koñcowej.


Procedura, która oblicza istnienie ścieżki o długości co najwyżej <math>n</math> ma do dyspozycji alternację i dokonuje tego w dwóch etapach.
Procedura, która oblicza istnienie ¶cie¿ki o d³ugo¶ci co najwy¿ej <math>n</math> ma do dyspozycji alternacjê i dokonuje tego w dwóch etapach.
W pierwszym zgaduje wierzchołek pośredni
W pierwszym zgaduje wierzcho³ek po¶redni
<math>t</math> na ścieżce działając w trybie "OR". Następnie przełącza się w tryb uniwersalny "AND" i sprawdza rekurencyjnie,
<math>t</math> na ¶cie¿ce dzia³aj±c w trybie "OR". Nastêpnie prze³±cza siê w tryb uniwersalny "AND" i sprawdza rekurencyjnie,
czy obydwie części ścieżki, długości <math>n/2</math> poprzez odgadnięty wierzchołek <math>t</math> istnieją.
czy obydwie czê¶ci ¶cie¿ki, d³ugo¶ci <math>n/2</math> poprzez odgadniêty wierzcho³ek <math>t</math> istniej±.


Czas potrzebny do działania to głębokość rekurencji, czyli  log <math>(c^{f(n)})</math> co jest rzędu <math>f(n)</math> przemnożony
Czas potrzebny do dzia³ania to g³êboko¶æ rekurencji, czyli  log <math>(c^{f(n)})</math> co jest rzêdu <math>f(n)</math> przemno¿ony
przez czas potrzebny do przetworzenia każdego kroku, który wynosi również <math>f(n)</math>, gdyż jest to rozmiar konfiguracji. Łącznie daje to czas<math>f^2(n)</math>.
przez czas potrzebny do przetworzenia ka¿dego kroku, który wynosi równie¿ <math>f(n)</math>, gdy¿ jest to rozmiar konfiguracji. £±cznie daje to czas<math>f^2(n)</math>.
Zwróćmy uwagę, że liczymy czas na ''jednej'' ścieżce obliczeń, dzięki realizacji rekurencji przy pomocy alternacji!
Zwróæmy uwagê, ¿e liczymy czas na ''jednej'' ¶cie¿ce obliczeñ, dziêki realizacji rekurencji przy pomocy alternacji!


Ad. 3:<br>
Ad. 3:<br>
Weźmy dowolny język <math>L\in</math> ASPACE <math>(f(n))</math> akceptowany przez alternującą maszynę Turinga <math>M</math>.
We¼my dowolny jêzyk <math>L\in</math> ASPACE <math>(f(n))</math> akceptowany przez alternuj±c± maszynê Turinga <math>M</math>.
Mamy do dyspozycji czas rzędu wykładniczego względem <math>f(n)</math>, a więc możemy wygenerować cały graf konfiguracji
Mamy do dyspozycji czas rzêdu wyk³adniczego wzglêdem <math>f(n)</math>, a wiêc mo¿emy wygenerowaæ ca³y graf konfiguracji
obliczeń maszyny <math>M</math> (który jak wiemy ma rozmiar <math>c^{f(n)}</math>, gdy <math>f(n)\geqslant </math> log <math>n</math>).
obliczeñ maszyny <math>M</math> (który jak wiemy ma rozmiar <math>c^{f(n)}</math>, gdy <math>f(n)\geqslant </math> log <math>n</math>).
Następnie stosownie do typów "AND" i "OR" przeglądamy graf od konfiguracji końcowych i decydujemy
Nastêpnie stosownie do typów "AND" i "OR" przegl±damy graf od konfiguracji koñcowych i decydujemy
o akceptacji słowa wejściowego.
o akceptacji s³owa wej¶ciowego.
}}
</div>}}</div>


{{cwiczenie||
{{cwiczenie||
Udowodnij, że problemy TSP(D) i EXACT TSP są wielomianowo równoważne.
Udowodnij, ¿e problemy TSP(D) i EXACT TSP s± wielomianowo równowa¿ne.
}}
}}


{{wskazowka|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka ||| <div class="mw-collapsible-content" style="display:none">
Skorzystaj z problemu HAMILTON PATH.
Skorzystaj z problemu HAMILTON PATH.
}}
</div>}}</div>


{{rozwiazanie||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie ||<div class="mw-collapsible-content" style="display:none">
Załóżmy, że TSP(D) ma rozwiązanie wielomianowe. Dzięki opisywanej już metodzie wyszukiwania binarnego możemy
Za³ó¿my, ¿e TSP(D) ma rozwi±zanie wielomianowe. Dziêki opisywanej ju¿ metodzie wyszukiwania binarnego mo¿emy
odnaleźć <math>K</math> - optymalny koszt dzięki temu, że potrzebujemy zadać tylko logarytmiczną liczbę pytań względem <math>K</math>,
odnale¼æ <math>K</math> - optymalny koszt dziêki temu, ¿e potrzebujemy zadaæ tylko logarytmiczn± liczbê pytañ wzglêdem <math>K</math>,
czyli liniową względem rozmiaru wejścia.
czyli liniow± wzglêdem rozmiaru wej¶cia.


Niewiele trudniejsza jest implikacja w drugą stronę. Załóżmy, że EXACT TSP ma rozwiązanie wielomianowe. Metoda wyszukiwania
Niewiele trudniejsza jest implikacja w drug± stronê. Za³ó¿my, ¿e EXACT TSP ma rozwi±zanie wielomianowe. Metoda wyszukiwania
binarnego tym razem zawodzi. Zgodnie ze wskazówką rozwiążemy najpierw HAMILTON PATH. Mając dany graf skierowany <math>G</math> w którym
binarnego tym razem zawodzi. Zgodnie ze wskazówk± rozwi±¿emy najpierw HAMILTON PATH. Maj±c dany graf skierowany <math>G</math> w którym
chcemy znaleźć ścieżkę Hamiltona konstruujemy przykład <math>G'</math> dla EXACT TSP. Jeśli krawędź istnieje w <math>G</math> to w <math>G'</math> otrzymuje wagę
chcemy znale¼æ ¶cie¿kê Hamiltona konstruujemy przyk³ad <math>G'</math> dla EXACT TSP. Je¶li krawêd¼ istnieje w <math>G</math> to w <math>G'</math> otrzymuje wagê
1, jeśli nie istnieje w <math>G</math> to w <math>G'</math> wstawiamy ją z wagą 2. Łatwo stwierdzić, że graf <math>G</math> ma ścieżkę Hamiltona wtedy i tylko wtedy,
1, je¶li nie istnieje w <math>G</math> to w <math>G'</math> wstawiamy j± z wag± 2. £atwo stwierdziæ, ¿e graf <math>G</math> ma ¶cie¿kê Hamiltona wtedy i tylko wtedy,
gdy trasa komiwojażera w <math>G'</math> ma koszt dokładnie <math>n</math> -- rozmiar grafu.
gdy trasa komiwoja¿era w <math>G'</math> ma koszt dok³adnie <math>n</math> -- rozmiar grafu.


Ponieważ HAMILTON PATH jest NP-zupełny, więc istnieje redukcja TSP(D) do HAMILTON PATH, a tym samym składając redukcje otrzymamy algorytm
Poniewa¿ HAMILTON PATH jest NP-zupe³ny, wiêc istnieje redukcja TSP(D) do HAMILTON PATH, a tym samym sk³adaj±c redukcje otrzymamy algorytm
wielomianowy dla TSP(D).
wielomianowy dla TSP(D).
}}
</div>}}</div>


==Testy końcowe==
==Testy koñcowe==

Wersja z 20:36, 27 lip 2006

Przedmiot & Z³o¿ono¶æ obliczeniowa

Modu³ & 13

Tytu³ & Pamiêæ logarytmiczna i hierarchia wielomianowa

Opracowanie & Przemys³aw Broniek

{ Syllabus}

Pamiêæ logarytmiczna i hierarchia wielomianowa

  • klasy L, NL i coNL,
  • Twierdzenie Immermana-Szelepcsényi'ego,
  • klasy coNP i DP,
  • maszyny alternuj±ce,
  • hierarchia wielomianowa.

Klasy L, NL i coNL

W tym rozdziale zajmiemy siê klasami z³o¿ono¶ci, w których dajemy bardzo restrykcyjne wymagania odno¶nie zu¿ywanej pamiêci, a mianowicie ograniczamy jej ilo¶æ przez funkcjê logarytmiczn±. Przypomnijmy:

  • Klasa L = SPACE(logn), to klasa tych jêzyków, które mog± byæ akceptowane w deterministycznej pamiêci logarytmicznej,
  • Klasa NL = NSPACE(logn), to klasa tych jêzyków, które mog± byæ akceptowane w niedeterministycznej pamiêci logarytmicznej,
  • Klasa coNL = coNSPACE(logn), to dope³nienie klasy tych jêzyków, które mog± byæ akceptowane w niedeterministycznej pamiêci logarytmicznej,

Na podstawie nastêpnego rozdzia³u i twierdzenia Immermana-Szelepcsényi'ego dowiemy siê, ¿e NL=coNL . Natomiast pytanie czy L=NL pozostaje wci±¿ problemem otwartym.

Przyjrzymy siê teraz problemom zupe³nym w klasie NL. Zupe³no¶æ definiujemy przy pomocy redukcji w pamiêci logarytmicznej, gdy¿ jak wiemy, wszystkie z powy¿szych klas s± zawarte w klasie P (chocia¿ nie wiemy, czy ¶ci¶le). Dopuszczenie redukcji wielomianowej zniwelowa³oby jakiekolwiek ró¿nice pomiêdzy jêzykami, gdy¿ sama redukcja mia³aby moc obliczeniow± pozwalaj±c± rozwi±zaæ wszystkie problemy z tych klas. Poni¿szy problem okazuje siê byæ NL-zupe³ny:

Definicja [Uzupelnij]

Problem REACHABILITY:
Wej¶cie: Graf skierowany G oraz wierzcho³ki x i y.
Wyj¶cie: Czy istnieje ¶cie¿ka od x do y w G?

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

Bardzo ciekawy rezultat, który zbli¿y³ nas do odpowiedzi na pytanie czy L=NL, uzyska³ w 2004 Reingold. Pokaza³ on, ¿e problem UNDIRECTED REACHABILITY, czyli osi±galno¶æ w grafie nieskierowanym nale¿y do klasy L.

Twierdzenie Immermana-Szelepcsényi'ego

Ten rozdzia³ po¶wiêcony jest bardzo ciekawemu i ca³kiem m³odemu wynikowi udowodnionemu niezale¿nie przez Neila Immermana i Róberta Szelepcsényi'ego w roku 1987, za który otrzymali w 1995 nagrodê Gödel'a.

Twierdzenie mówi o tym, ¿e klasy niedeterministyczne z³o¿ono¶ci pamiêciowej s± zamkniête na dope³nienie:

Twierdzenie [Uzupelnij]

{{{3}}}

Dowód [Uzupelnij]

{{{3}}}

Klasy coNP i DP

Wprowadzili¶my ju¿ zarówno klasê NP jak i pojêcie dope³nieñ klas. Przyjrzyjmy siê bli¿ej klasie coNP. Klasa NP, jest to zbiór tych jêzyków, dla których mo¿emy ³atwo weryfikowaæ przynale¿no¶æ s³ów. Klasa coNP natomiast, to zbiór tych jêzyków, dla których mo¿emy ³atwo weryfikowaæ, ¿e s³owo nie nale¿y do jêzyka.

Podobnie jak dla NP i twierdzenia Fagina, mo¿na scharakteryzowaæ coNP jako zbiór w³asno¶ci teoriografowych wyra¿alnych w uniwersalnej logice drugiego rzêdu.

Oto przyk³ady problemów z klasy coNP:

Definicja [Uzupelnij]

Problem TAUTOLOGY:
Wej¶cie: formu³a logiczna ϕ jak dla problemu SAT.
Wyj¶cie: czy ka¿de warto¶ciowanie spe³nia ϕ?

Definicja [Uzupelnij]

Problem HAMILTON PATH COMPLEMENT:
Wej¶cie: graf nieskierowany G.
Wyj¶cie: czy G nie zawiera ¶cie¿ki Hamiltona?

W powy¿szych problemach weryfikacja negatywna s³owa wej¶ciowego jest ³atwa, bo opiera siê na zgadniêciu warto¶ciowania niespe³niaj±cego lub ¶cie¿ki Hamiltona.

Nietrudno udowodniæ (patrz æwiczenie koñcowe), ¿e s± to problemy zupe³ne dla klasy coNP. Nie jest to nic zaskakuj±cego, bowiem równie prosto mo¿na udowodniæ, ¿e je¿eli L jest NP-zupe³ny, to jego dope³nienie L‾ jest coNP-zupe³ne.

Jak wiele pytañ w teorii z³o¿ono¶ci obliczeniowej równie¿ i to, czy NP=coNP pozostaje otwarte. Mo¿emy jedynie stwierdziæ, ¿e je¿eli P=NP, to NP=coNP, gdy¿ P jest zamkniêta na dope³nienie. Jednak ju¿ implikacja w drug± stronê nie jest znana. Inna podobna implikacja to:

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

Poni¿szy rysunek przedstawia relacje pomiêdzy poznanymi klasami i omawian± za chwilê klas± DP:

{1cm}

[width=10cm]{ZO-13-1-rys.jpg}
Relacje pomiêdzy klasami NP, coNP i DP

{1cm}

Oczywi¶cie przygl±daj±c siê wszystkim takim rysunkom nale¿y pamiêtaæ, ¿e mog± one w wielu miejscach kolapsowaæ.

Klasa DP

Zastanówmy siê nad nastêpuj±cym problemem:

Przykład [Uzupelnij]

Problem EXACT TSP:
Wej¶cie: graf nieskierowany wa¿ony G i liczba K
Wyj¶cie: czy optymalna trasa komiwoja¿era dla G ma warto¶æ dok³adnie K?

Jest to wersja dok³adna znanego problemu optymalizacyjnego -- problemu komiwoja¿era. Wiemy ¿e wersja decyzyjna TSP(D) jest NP-zupe³na. Nietrudno pokazaæ równie¿, ¿e EXACT TSP i TSP(D) s± wielomianowo równowa¿ne (æwiczenie koñcowe), tzn., ¿e je¶li jeden z nich ma rozwi±zanie w czasie wielomianowym to drugi te¿. W tym rozdziale sklasyfikujemy z³o¿ono¶æ EXACT TSP dok³adniej przy pomocy klasy DP. Nie umiemy bowiem pokazaæ, ¿e EXACT TSP nale¿y do NP, wszak jak po¶wiadczyæ i szybko zweryfikowaæ, ¿e d³ugo¶æ optymalnej trasy wynosi dok³adnie K? Widzimy, ¿e odpowied¼ na to pytanie wymaga stwierdzenia, ¿e trasa ma d³ugo¶æ co najmniej K i co najwy¿ej K, co sugeruje pewne specyficzne po³±czenie problemu TSP(D) i jego dope³nienia.

Definicja [Uzupelnij]

Klasa DP to zbiór jêzyków L takich, ¿e L=L1∩L2, gdzie L1∈NP natomiast L2∈coNP.

Przy tak postawionej definicji EXACT TSP nale¿y do DP. Jest on bowiem przeciêciem jêzyka TSP(D) i TSP(D) COMPLEMENT, tzn. koszt trasy wynosi dok³adnie K, gdy jest równy co najwy¿ej K (to przynale¿no¶æ do TSP(D)) oraz co najmniej K (to przynale¿no¶æ s³owa do TSP(D) COMPLEMENT).

Klasa DP posiada problemy zupe³ne. Rozwa¿my problem nastêpuj±cy:

Przykład [Uzupelnij]

Problem SAT-UNSAT:
Wej¶cie: formu³y logiczne ϕ i ψ jak dla SAT.
Wyj¶cie: czy formu³a ϕ jest spe³nialna, natomiast ψ niespe³nialna?

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

Równie¿ wspomniany na pocz±tku problem EXACT TSP jest DP-zupe³ny. Mo¿na rozwa¿aæ tak¿e wiele innych wersji EXACT znanych problemów NP-zupe³nych, które okazuj± siê DP-zupe³ne.

Klasa DP zawiera tak¿e problemy DP-zupe³ne innego rodzaju:

Przykład [Uzupelnij]

Problem CRITICAL SAT:
Wej¶cie: formu³a logiczna ϕ jak dla SAT.
Wyj¶cie: czy formu³a ϕ jest nie spe³nialna, natomiast usuniêcie dowolnej klauzuli sprawia, ¿e jest spe³nialna?

Przykład [Uzupelnij]

Problem CRITICAL HAMILTON PATH:
Wej¶cie: graf nieskierowany G
Wyj¶cie: czy G nie ma ¶cie¿ki Hamiltona, natomiast dodanie dowolnej krawêdzi do G powoduje, ¿e ju¿ j± posiada?

Maszyny alternuj±ce

W tym rozdziale przedstawimy ciekawe uogólnienie niedeterminizmu, zwane alternacj±. Przypomnijmy, ¿e maszyna niedeterministyczna akceptuje s³owo, gdy na którejkolwiek ze ¶cie¿ek obliczeñ trafi do stanu akceptuj±cego.

Maszyna alternuj±ca ma wiêcej mo¿liwo¶ci. Ka¿dy z jej stanów jest oznaczony poprzez "AND" lub "OR", które nazywamy odpowiednio stanami uniwersalnymi i egzystencjalnymi.

Gdy maszyna jest w stanie typu "OR", to dokonuje akceptacji gdy dowolna ze ¶cie¿ek obliczeñ wychodz±cych z niego akceptuje s³owo. Tak w³a¶nie dzia³aj± zawsze zwyk³e maszyny niedeterministyczne.

Stany typu "AND" s± rozszerzaj± t± funkcjonalno¶æ. Maszyna dokonuje akceptacji bêd±c w takim stanie, gdy ka¿da ze ¶cie¿ek obliczeñ wychodz±cych z tego stanu jest akceptuj±ca.

Miarê z³o¿ono¶ci czasowej i pamiêciowej maszyn alternuj±cych definiujemy zupe³nie tak jak dla maszyn niedeterministycznych, tzn. funkcja f(n) jest miar± z³o¿ono¶ci czasowej, gdy ka¿da ze ¶cie¿ek obliczeñ ma d³ugo¶æ ograniczon± przez f(n) oraz z³o¿ono¶æ pamiêciow± f(n) gdy na ka¿dej ze ¶cie¿ek obliczeñ maszyna zu¿ywa co najwy¿ej f(n) pamiêci.

Definicja [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \textsc{ATIME}(f(n))} oznaczamy zbiór jêzyków L takich, ¿e s± akceptowane przez alternuj±c± maszynê Turinga M o z³o¿ono¶ci czasowej f(n).

Definicja [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \textsc{ASPACE}(f(n))} oznaczamy zbiór jêzyków L takich, ¿e s± akceptowane przez alternuj±c± maszynê Turinga M o z³o¿ono¶ci pamiêciowej f(n).

Wprowadzamy te¿ skróty dla najpopularniejszych klas:

  • Klasa AP = ATIME (nk)=⋃j>0 ATIME (nj), to klasa tych jêzyków, które mog± byæ akceptowane w alternuj±cym czasie wielomianowym,
  • Klasa AL = ASPACE(logn), to klasa tych jêzyków, które mog± byæ akceptowane w alternuj±cej pamiêci logarytmicznej,

Nietrudno siê domy¶liæ, ¿e alternacja jest silniejsza ni¿ niedeterminizm z definicji dzia³ania maszyn. Wiemy zatem, w szczególno¶ci, ¿e AP zawiera w sobie NP. Poni¿sze æwiczenie pokazuje, ¿e o AP mo¿na powiedzieæ wiêcej:

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

To jednak nie wszystko co potrafi klasa AP. Znajduj± siê w niej jêzyki, o których nie wiemy czy nale¿± do NP lub coNP.

Definicja [Uzupelnij]

Problem MIN-FORMULA:
Wej¶cie: formu³a logiczna ϕ jak dla problemu SAT.
Wyj¶cie: czy ϕ jest minimalna, tzn. czy ¿adna krótsza formu³a nie jest jej równowa¿na?

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

Teraz przedstawimy kilka relacji pomiêdzy klasami obliczeñ alternuj±cych:

Twierdzenie [Uzupelnij]

Nastêpuj±ce relacje s± prawdziwe:

  1. Je¶li f(n)⩾n to ATIME (f(n))⊆ SPACE (f(n)),
  1. Je¶li f(n)⩾n to SPACE (f(n))⊆ ATIME (f2(n)),
  1. Je¶li f(n)⩾ log n to ASPACE (f(n))⊆ TIME (cf(n)).
  1. Je¶li f(n)⩾ log n to ASPACE (f(n))⊇ TIME (cf(n)).

Dowód [Uzupelnij]

{{{3}}}

Dziêki wymienionym relacjom pomiêdzy klasami alternuj±cymi mo¿emy udowodniæ kilka dok³adnych równo¶ci pomiêdzy klasami, a to rzadka rzecz w teorii z³o¿ono¶ci. Wiemy zatem, ¿e:

  • AL=P,
  • APSPACE = EXP,
  • AP=PSPACE.

Hierarchia wielomianowa

W tej czê¶ci zdefiniujemy ca³± hierarchiê klas ponad znanymi nam ju¿ P i NP, która stanowi pewne uogólnienie problematyki spotkanej w klasie DP.

W poprzednich rozdzia³ach zdefiniowali¶my pojêcie maszyny z wyroczni± na jêzyk L oznaczanej przez ML. Przypomnijmy, ¿e jest to zwyk³a maszyna M z dodatkow± mo¿liwo¶ci± zadania pytania postaci "czy x∈L?" które kosztuje jedn± jednostkê czasu. Rozszerzenie tego pojêcia na klasy jest naturalne. Poprzez PNP oznaczamy zbiór tych jêzyków, które mog± byæ rozstrzygane przez maszyny z klasy P z wyroczni± na dowolny jêzyk z klasy NP.

Ta klasa okazuje siê byæ mocniejsza od DP, bowiem w DP mogli¶my zadañ pytanie tylko raz (dotycz±ce coNP, ale w sensie wyroczni dzia³a to jak pytanie do NP), a tutaj dowoln± liczbê razy i to na dodatek pytañ adaptywnych, tzn. takich, które mog± zale¿eæ od wyników odpowiedzi na poprzednie z nich. Kolejn± interesuj±c± klas± jest NPNP. Wszystkie te klasy daj± nam coraz wiêksze mo¿liwo¶ci, lecz oczywi¶cie nie wiadomo, czy s± to ¶ci¶le wiêksze klasy, choæ panuje takie przekonanie:

{1cm}

[width=10cm]{ZO-13-3-rys.jpg}
Klasy relatywne

{1cm}

Postêpuj±c w ten sposób Meyer i Stockmeyer w latach 70 zdefiniowali ca³± hierarchiê klas:

Definicja [Uzupelnij]

Hierarchia wielomianowa, to ci±g klas indeksowany poprzez i:

  • ∑0P=∏0P=Δ0P=P
  • Δi+1P=P∑iP, dla i>0,
  • ∑i+1P=NP∑iP, dla i>0,
  • ∏i+1P=coNP∑iP, dla i>0.

Dodatkowo poprzez PH oznaczamy sumê wszystkich tych klas, czyli:
PH=⋃i⩾0∑iP.

Poniewa¿ na poziomie zerowym wszystkie elementy hierarchii to P, wiêc na poziomie pierwszym, poniewa¿ taka wyrocznia nic nie daje, otrzymujemy Δ1P=P,∑1P=NP,∏1P=coNP. Drugi poziom, to klasyΔ2P=PNP,∑2P=NPNP,∏2P=coNPNP. Warto zwróciæ uwagê, ¿e ∏iP jest dope³nieniem ∑iP na ka¿dym poziomie wprost z definicji. Zawieranie siê poszczególnych elementów na jednym poziomie obrazuje poni¿szy rysunek:

{1cm}

[width=10cm]{ZO-13-4-rys.jpg}
Hierarchia wielomianowa

{1cm}

Do tej pory czêsto odwo³ywali¶my siê do odpowiednio¶ci pomiêdzy klas± NP a szczególnymi relacjami wielomianowo zrównowa¿onymi i rozstrzygalnymi. Przedstawimy teraz zgrabn± charakteryzacjê klas z hierarchii wielomianowej przy pomocy podobnego kryterium:

Twierdzenie [Uzupelnij]

Niech L bêdzie jêzykiem, i>0. Jêzyk L nale¿y do ∑iP wtedy i tylko wtedy, gdy istnieje wielomianowo zrównowa¿ona i rozstrzygalna relacja R (i+1-argumentowa), taka, ¿e x∈L dok³adnie wtedy, gdy ∃y1∀y2∃y3…Qyi takie, ¿e R(x,y1,…,yi) jest spe³nione (i-ty kwantyfikator jest uniwersalny, gdy i jest parzyste, natomiast egzystencjalny, gdy i jest nieparzyste).

Hierarchia wielomianowa jest struktur± dosyæ wra¿liw± na kolapsy, tzn. równo¶ci klas na pewnym poziomie. Okazuje siê, ¿e wtedy przenosz± siê one automatycznie w górê:

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

Zachodzi równie¿ podobny fakt. Otó¿, je¶li P=NP (albo tylko NP=coNP), to hierarchia kolapsuje ju¿ na pierwszym poziomie.

Mo¿na by siê zastanowiæ, czy kolejne poziomy hierarchii wielomianowej s± interesuj±ce z punku widzenia problemów, które pozwalaj± one rozwi±zaæ. Okazuje siê, ¿e na ka¿dym poziomie hierarchii posiada ona problemy zupe³ne:

Definicja [Uzupelnij]

Problem QSAT i:
Wej¶cie: formu³a logiczna ϕ jak dla problemu SAT poprzedzona i naprzemiennymi grupami kwantyfikatorów egzystencjalnych i uniwersalnych: Φ=∃x1∀x2∃x3…Qxiϕ.
Wyj¶cie: czy Φ jest prawdziwa?

Twierdzenie [Uzupelnij]

Problem QSATi jest ∑iP-zupe³ny dla i>0.

Jednak pytanie czy istnieje problem PH-zupe³ny (czyli zupe³ny dla ca³ej hierarchii) jest otwarte i panuje przekonanie, ¿e tak nie jest, gdy¿:

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

Jak silna jest ca³a hierarchia? Mo¿na ³atwo zauwa¿yæ, ¿e zawiera siê ona w znanej ju¿ nam klasie PSPACE, ze wzglêdu na fakt, ¿e mo¿na ³atwo rozstrzygaæ w wielomianowej pamiêci relacje, charakteryzuj±ce problemy z PH, które opisywali¶my wcze¶niej.

Jak nietrudno siê domy¶liæ pytanie, czy PH=PSPACE jest otwarte. Bardzo interesuj±ce jest jednak, ¿e gdyby równo¶æ zachodzi³a, to poniewa¿ PSPACE zawiera problemy zupe³ne, to PH równie¿ by je zawiera³a, st±d zapad³a by siê na pewnym skoñczonym poziomie. St±d przekonanie, ¿e PH zawiera siê silnie w PSPACE.

Na koniec ciekawy rezultat autorstwa Seinosuke Tody (laureata nagrody Gödel'a z roku 1998) zwi±zany z klas± PH. Pokaza³ on, ¿e PH⊆PPP, czyli wyrocznia na klasê PP jest niesamowicie silna i pozwala poch³on±æ tak misternie zbudowan± piramidê coraz silniejszych klas.

Æwiczenia dodatkowe

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

Ćwiczenie

{{{3}}}
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}

Testy koñcowe

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_Arka&oldid=6967”