Test Arka: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Arek (dyskusja | edycje)
687 edycji
Nie podano opisu zmian
m Zastępowanie tekstu – „\displaystyle ” na „”
 
(Nie pokazano 77 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
Przedmiot & '''Z³o¿ono¶æ obliczeniowa''' <br>
<quiz type="exclusive">
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>
==Testy==


Modu³ &  '''13''' <br>
<quiz type="exclusive">
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>


Tytu³ &  '''Pamiêæ logarytmiczna i hierarchia wielomianowa''' <br>
<quiz>
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>


Opracowanie & '''Przemys³aw Broniek''' <br>
<quiz type="exclusive">
In C++, 14 % 4 =
<option reply="Za mało">1</option>
<option>2</option>
<option reply="Za dużo">3</option>
<wrongoption reply="O wiele za dużo">4</wrongoption>
</quiz>
   
<quiz>
In C++, 14 % 4 =
<option reply="Za mało">1</option>
<option>2</option>
<option reply="Za dużo">3</option>
<wrongoption reply="O wiele za dużo">4</wrongoption>
</quiz>


{ Syllabus}
<quiz>
Variables that are declared, but not initialized, contain
<wrongoption>blank spaces</wrongoption>
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
</quiz>


Pamiêæ logarytmiczna i hierarchia wielomianowa
<quiz type="exclusive">
Variables that are declared, but not initialized, contain
<wrongoption>blank spaces</wrongoption>
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
</quiz>


* klasy L, NL i coNL,


* Twierdzenie Immermana-Szelepcsényi'ego,
<div style="background-color: #bbbbbb; padding: 2em; border: 1px solid black">
Dlaczego suma <math>\sum_{i=1}^{10}i</math> jest źle wyświetlana w wykładniku potęgi?


* klasy coNP i DP,
<math>z^{\sum_{i=1}^{10}i}</math>


* maszyny alternuj±ce,


* hierarchia wielomianowa.
</div>


==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
<div id="content">
pamiêci, a mianowicie ograniczamy jej ilo¶æ przez funkcjê logarytmiczn±. Przypomnijmy:
<div id="navcontainer">
<ul id="navlist">
<div><a href="index.xml" class="withChild">Start</a></div>


* Klasa L = SPACE(log<math>n</math>), to klasa tych jêzyków, które mog± byæ akceptowane w deterministycznej pamiêci logarytmicznej,
<div id="active" class="withoutChild">Zadanie 1.</div>
<div><a href="zadanie_2.xml" class="withoutChild">Zadanie 2.</a></div>
<div><a href="zadanie_3.xml" class="withoutChild">Zadanie 3.</a></div>
<div><a href="zadanie_4.xml" class="withoutChild">Zadanie 4.</a></div>
<div><a href="zadanie_5.xml" class="withoutChild">Zadanie 5.</a></div>
<div><a href="zadanie_6.xml" class="withoutChild">Zadanie 6.</a></div>


* Klasa NL = NSPACE(log<math>n</math>), to klasa tych jêzyków, które mog± byæ akceptowane w niedeterministycznej pamiêci logarytmicznej,
</ul>
</div>
<div id="main">
<div id="nodeDecoration">
<p id="nodeTitle">Zadanie 1.</p>
</div>
<script type="text/javascript" src="common.js"></script> <script
type="text/javascript" src="libot_drag.js"></script>
<div class="iDevice emphasis1"><img alt="Ikona obiektu Pytanie"
class="iDevice_icon" src="icon_question.gif" /> <span
class="iDeviceTitle">Zadanie 1,</span><br />
<div class="iDevice_inner">
Liczba <math><msqrt><mrow><mn>3</mn>


* 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,
<mo class="MathClass-bin">+</mo> <mn>2</mn><msqrt><mrow>
<mn>2</mn></mrow></msqrt></mrow></msqrt> <mo class="MathClass-bin">&minus;</mo><msqrt><mrow><mn>3</mn>
<mo class="MathClass-bin">&minus;</mo> <mn>2</mn><msqrt><mrow>
<mn>2</mn></mrow></msqrt></mrow></msqrt></math> &nbsp;&nbsp;
<table>
<tbody>


Na podstawie nastêpnego rozdzia³u i twierdzenia Immermana-Szelepcsényi'ego dowiemy siê, ¿e  NL=coNL . Natomiast pytanie czy L=NL pozostaje
<tr>
wci±¿ problemem otwartym.
<td><input type="checkbox" name="option9" id="ia0b9"
value="vTrue"
onclick="document.getElementById('sa0b9').style.display = this.checked ? 'block' : 'none';" /></td>
<td>jest dodatnia</td>
<td>
<div id="sa0b9" style="color: rgb(0, 51, 204);display: none;">Poprawnie</div>
</td>
</tr>
<tr>


Przyjrzymy siê teraz problemom zupe³nym w klasie NL. Zupe³no¶æ definiujemy przy pomocy redukcji w pamiêci logarytmicznej, gdy¿
<td><input type="checkbox" name="option9" id="ia1b9"
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,
value="vTrue"
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:
onclick="document.getElementById('sa1b9').style.display = this.checked ? 'block' : 'none';" /></td>
<td>jest wymierna</td>
<td>
<div id="sa1b9" style="color: rgb(0, 51, 204);display: none;">Poprawnie</div>
</td>
</tr>
<tr>
<td><input type="checkbox" name="option9" id="ia2b9"
value="vFalse"
onclick="document.getElementById('sa2b9').style.display = this.checked ? 'block' : 'none';" /></td>


{{definicja|[Uzupelnij]||
<td>nale&raquo;y do tr&oacute;jkowego zbioru Cantora.</td>
Problem REACHABILITY:<br>
<td>
Wej¶cie: Graf skierowany <math>G</math> oraz wierzcho³ki <math>x</math> i <math>y</math>.<br>
<div id="sa2b9" style="color: rgb(0, 51, 204);display: none;">Źle</div>
Wyj¶cie: Czy istnieje ¶cie¿ka od <math>x</math> do <math>y</math> w <math>G</math>?
</td>
}}
</tr>
</tbody>
</table>


{{cwiczenie||
</div>
Poka¿, ¿e problem REACHABILITY jest NL-zupe³ny.
</div>
}}
<div class="noprt" align="right"><a href="index.xml">&laquo;
 
previous</a> | <a href="zadanie_2.xml">next &raquo;</a></div>
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka  ||| <div class="mw-collapsible-content" style="display:none">
</div>
Zwróæ uwagê na fakt, ¿e problem REACHABILITY jest zwi±zany z wykonywaniem obliczeñ przez maszynê Turinga.
</div>
</div>}}</div>
 
<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.
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
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 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.
 
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.
 
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
<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>,
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> .
Nie potrzebujemy konstruowaæ ca³ego grafu, a jedynie stwierdzaæ, czy dwie konfiguracje s± s±siednie, co mo¿emy zrobiæ
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
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]||
(twierdzenie Immermana-Szelepcsényi'ego)
Je¶li <math>f(n)</math> jest konstruowalna pamiêciowo, to NSPACE(f(n))=coNSPACE(f(n)).
}}
 
{{dowod|[Uzupelnij]||
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>.
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,
¿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ê").
 
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>,
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
<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
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>i:=1</math> to <math>n</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:
 
{<math>s(i):=0</math>}
{<math>v\in V(G)</math>}
{<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,
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.
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
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
czy <math>v\in S(i)</math>:
 
{<math>licznik:=0, wynik:=NIE</math>}
{<math>u\in V(G)</math>}
{<math>u\in S(i-1)</math>}
{licznik++}
{<math>u=v</math> lub <math>u\rightarrow v \in G</math>}{wynik:=TAK}
 
{<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
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)
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>:
 
{<math>p_1:=x</math>}
{<math>i := 2</math> to <math>k</math>}
{zgadnij <math>p_i</math>}
{<math>p_{i-1}\neq p_i</math> i nie zachodzi <math>p_{i-1}\rightarrow p_i \in G</math>}{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ê
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
<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¿
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>.
 
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.
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
<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
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==
 
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:<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>?
}}
 
{{definicja|[Uzupelnij]||
Problem HAMILTON PATH COMPLEMENT:<br>
Wej¶cie: graf nieskierowany <math>G</math>.<br>
Wyj¶cie: czy <math>G</math> 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 <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.
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:
 
{{cwiczenie||
Je¶li <math>L</math> jest coNP-zupe³ny i <math>L\in NP</math> to NP=coNP.
}}
 
<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.
</div>}}</div>
 
<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.
 
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
<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,
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.
</div>}}</div>
 
Poni¿szy rysunek przedstawia relacje pomiêdzy poznanymi klasami i omawian± za chwilê klas± DP:
 
{1cm}
 
[width=10cm]{ZO-13-1-rys.jpg}<br>
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:
 
{{przyklad|[Uzupelnij]||
Problem EXACT TSP:<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>?
}}
 
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 <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.
 
{{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>.
}}
 
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).
 
Klasa DP posiada problemy zupe³ne. Rozwa¿my problem nastêpuj±cy:
 
{{przyklad|[Uzupelnij]||
Problem SAT-UNSAT:<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?
}}
 
{{cwiczenie||
Udowodnij, ¿e problem SAT-UNSAT jest DP-zupe³ny.
}}
 
<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.
</div>}}</div>
 
<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.
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æ.
 
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>
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.
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.
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:
 
{{przyklad|[Uzupelnij]||
Problem CRITICAL 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?
}}
 
{{przyklad|[Uzupelnij]||
Problem CRITICAL HAMILTON PATH:<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?
}}
 
==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 <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.
 
{{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
czasowej <math>f(n)</math>.
}}
 
{{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
pamiêciowej <math>f(n)</math>.
}}
 
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 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
<math>AP</math> zawiera w sobie <math>NP</math>. Poni¿sze æwiczenie pokazuje, ¿e o AP mo¿na powiedzieæ wiêcej:
 
{{cwiczenie||
Poka¿, ¿e AP zawiera w sobie klasê coNP.
}}
 
<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.
</div>}}</div>
 
<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.
 
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
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.
 
{{definicja|[Uzupelnij]||
Problem MIN-FORMULA:<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?
}}
 
{{cwiczenie||
Poka¿, ¿e MIN-FORMULA nale¿y do AP.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka  ||| <div class="mw-collapsible-content" style="display:none">
Wykorzystaj dwa tryby alternacji.
</div>}}</div>
 
<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
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>.
 
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æ.
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
niemo¿liwe, st±d uzyskujemy sprzeczno¶æ.
</div>}}</div>
 
Teraz przedstawimy kilka relacji pomiêdzy klasami obliczeñ alternuj±cych:
 
{{twierdzenie|[Uzupelnij]||
 
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 </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>.
 
}}
 
{{dowod|[Uzupelnij]||
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
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æ:
 
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±
, 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
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 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}
 
[width=10cm]{ZO-13-2-rys.jpg}<br>
Zapis przebiegu obliczeñ
 
{1cm}
 
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.
 
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>.
 
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>.
}}
 
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 <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
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),
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
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}<br>
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 <math>i</math>:<br>
 
* <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>\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>.
 
Dodatkowo poprzez <math>PH</math> oznaczamy sumê wszystkich tych klas, czyli:<br>
<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¿ 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>.
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:
 
{1cm}
 
[width=10cm]{ZO-13-4-rys.jpg}<br>
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 <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
<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).
}}
 
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ê:
 
{{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>.
}}
 
<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>.
</div>}}</div>
 
<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
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
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
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
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.
 
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 <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:
<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?
}}
 
{{twierdzenie|[Uzupelnij]||
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¿:
 
{{cwiczenie||
Poka¿, ¿e je¶li istnieje problem PH-zupe³ny, to hierarchia zapada siê na pewnym poziomie.
}}
 
<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.
</div>}}</div>
 
<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>
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>.
</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
³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
<math>PH\subseteq P^{PP}</math>, czyli wyrocznia na klasê <math>PP</math> jest
niesamowicie silna i pozwala poch³on±æ tak misternie zbudowan±
piramidê coraz silniejszych klas.
 
==Æwiczenia dodatkowe==
 
{{cwiczenie||
Poka¿, ¿e problem TAUTOLOGY jest coNP-zupe³ny.
}}
 
<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.
</div>}}</div>
 
<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
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
, ¿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
coNP-zupe³no¶ci problemu TAUTOLOGY.
</div>}}</div>
 
{{cwiczenie||
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 </math> log <math>n</math> to  ASPACE <math>(f(n)) \subseteq </math> TIME <math>(c^{f(n)})</math>.
 
}}
 
<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. 2: skorzystaj z idei zaczerpniêtej z twierdzenia Savitcha.<br>
</div>}}</div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{rozwiazanie  ||<div class="mw-collapsible-content" style="display:none"><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>.
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
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
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
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
potrzebuje <math>f(n)</math> pamiêci, a wiêc <math>L\in</math> SPACE <math>(f(n))</math>.
 
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
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.
 
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
<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±.
 
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>.
Zwróæmy uwagê, ¿e liczymy czas na ''jednej'' ¶cie¿ce obliczeñ, dziêki realizacji rekurencji przy pomocy alternacji!
 
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>.
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>).
Nastêpnie stosownie do typów "AND" i "OR" przegl±damy graf od konfiguracji koñcowych i decydujemy
o akceptacji s³owa wej¶ciowego.
</div>}}</div>
 
{{cwiczenie||
Udowodnij, ¿e problemy TSP(D) i EXACT TSP s± wielomianowo równowa¿ne.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">{{wskazowka  ||| <div class="mw-collapsible-content" style="display:none">
Skorzystaj z problemu HAMILTON PATH.
</div>}}</div>
 
<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
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.
 
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
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,
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
wielomianowy dla TSP(D).
</div>}}</div>
 
==Testy koñcowe==

Aktualna wersja na dzień 08:57, 28 sie 2023

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

Testy

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

In C++, 14 % 4 =

1

2

3

4

In C++, 14 % 4 =

1

2

3

4

Variables that are declared, but not initialized, contain

blank spaces

zeros

"garbage" values

nothing - they are empty

Variables that are declared, but not initialized, contain

blank spaces

zeros

"garbage" values

nothing - they are empty


Dlaczego suma ∑i=110i jest źle wyświetlana w wykładniku potęgi?

z∑i=110i



Zadanie 1.

<script type="text/javascript" src="common.js"></script> <script type="text/javascript" src="libot_drag.js"></script>

<img alt="Ikona obiektu Pytanie"

class="iDevice_icon" src="icon_question.gif" /> Zadanie 1,

Liczba Parser nie mógł rozpoznać (błąd składni): {\displaystyle <msqrt><mrow><mn>3</mn> <mo class="MathClass-bin">+</mo> <mn>2</mn><msqrt><mrow> <mn>2</mn></mrow></msqrt></mrow></msqrt> <mo class="MathClass-bin">&minus;</mo><msqrt><mrow><mn>3</mn> <mo class="MathClass-bin">&minus;</mo> <mn>2</mn><msqrt><mrow> <mn>2</mn></mrow></msqrt></mrow></msqrt>}   

<tbody> </tbody>
<input type="checkbox" name="option9" id="ia0b9"

value="vTrue"

onclick="document.getElementById('sa0b9').style.display = this.checked ? 'block' : 'none';" />		 jest dodatnia
<input type="checkbox" name="option9" id="ia1b9"

value="vTrue"

onclick="document.getElementById('sa1b9').style.display = this.checked ? 'block' : 'none';" />		 jest wymierna
<input type="checkbox" name="option9" id="ia2b9"

value="vFalse"

onclick="document.getElementById('sa2b9').style.display = this.checked ? 'block' : 'none';" />		 nale»y do trójkowego zbioru Cantora.
<a href="index.xml">« previous</a> | <a href="zadanie_2.xml">next »</a>
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_Arka&oldid=79852”