Test Arka: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Arek (dyskusja | edycje)
687 edycji
m Zastępowanie tekstu – „\displaystyle ” na „”
 
(Nie pokazano 98 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
<math>\textnormal{log}(f(n))</math>
<quiz type="exclusive">
<math>log(f(n))</math>
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==


<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>


{article}
<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>


{}{0.5cm} {}{0.8cm} {}{ -0.4cm} {}{ -0.4cm} {}{1mm} 14.6pt
<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>


{} {} {}
<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>


{proof}{ ''Dowód: ''}{<math>\square</math>}
<quiz type="exclusive">
{hint}{ ''Wskazówka: ''}{}
Variables that are declared, but not initialized, contain
{sol}{ ''Rozwiązanie: ''}{}
<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>


{empty}


{ Informacje}
<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?


{|l|l|}
<math>z^{\sum_{i=1}^{10}i}</math>


Przedmiot & '''Złożoność obliczeniowa''' <br>


Moduł &  '''13''' <br>
</div>


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


Opracowanie &  '''Przemysław Broniek''' <br>
<div id="content">
<div id="navcontainer">
<ul id="navlist">
<div><a href="index.xml" class="withChild">Start</a></div>


{ Syllabus}
<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>


Pamięć logarytmiczna i hierarchia wielomianowa
</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>


* klasy L, NL i coNL,
<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>


* Twierdzenie Immermana-Szelepcsényi'ego,
<tr>
<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>


* klasy coNP i DP,
<td><input type="checkbox" name="option9" id="ia1b9"
value="vTrue"
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>


* maszyny alternujące,
<td>nale&raquo;y do tr&oacute;jkowego zbioru Cantora.</td>
<td>
<div id="sa2b9" style="color: rgb(0, 51, 204);display: none;">Źle</div>
</td>
</tr>
</tbody>
</table>


* hierarchia wielomianowa.
</div>
 
</div>
==Klasy L, NL i coNL==
<div class="noprt" align="right"><a href="index.xml">&laquo;
 
previous</a> | <a href="zadanie_2.xml">next &raquo;</a></div>
W tym rozdziale zajmiemy się klasami złożoności, w których dajemy bardzo restrykcyjne wymagania odnośnie zużywanej
</div>
pamięci, a mianowicie ograniczamy jej ilość przez funkcję logarytmiczną. Przypomnijmy:
</div>
 
* 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 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 <math>\textnormal{NL=coNL}</math>. 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:<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>?
}}
 
====Ćwiczenie====
 
Pokaż, że problem REACHABILITY jest NL-zupełny.
 
Zwróć uwagę na fakt, że problem REACHABILITY jest związany z wykonywaniem obliczeń przez maszynę Turinga.
 
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 <math>\textnormal{log}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 <math>\textnormal{log}n</math> to jak wiemy <math>c^{\textnormal{log}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.
 
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]|pitagoras|
(twierdzenie Immermana-Szelepcsényi'ego)
Jeśli <math>f(n)</math> jest konstruowalna pamięciowo, to NSPACE(f(n))=coNSPACE(f(n)).
}}
 
{{twierdzenie|[Uzupelnij]|pitagoras|
(twierdzenie Immermana-Szelepcsényi'ego)
Jeśli <math>f(n)</math> jest konstruowalna pamięciowo, to NSPACEfn=coNSPACEfn.
}}
 
{{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 <math>\textnormal{log}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 \textnormal{log}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 \textnormal{coNSPACE}(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:
 
====Ćwiczenie====
 
Jeśli <math>L</math> jest coNP-zupełny i <math>L\in NP</math> to NP=coNP.
 
Pokaż inkluzje w obie strony korzystając z symetrii klas.
 
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.
 
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?
}}
 
====Ćwiczenie====
 
Udowodnij, że problem SAT-UNSAT jest DP-zupełny.
 
Skorzystaj z redukcji języka z NP oraz dopełnienia języka z coNP do SAT.
 
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\textnormal{ jest spełnialna}\}</math> oraz  <math>L_1=\{(\phi,\psi):\psi\textnormal{ nie jest spełnialna}\}</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.
 
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 = <math>\textnormal{ATIME}(n^k) = \bigcup_{j>0} \textnormal{ATIME}(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:
 
====Ćwiczenie====
 
Pokaż, że AP zawiera w sobie klasę coNP.
 
Pokaż że problem coNP-zupełny TAUTOLOGY należy do 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.
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ą.
 
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?
}}
 
====Ćwiczenie====
 
Pokaż, że MIN-FORMULA należy do AP.
 
Wykorzystaj dwa tryby alternacji.
 
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ść.
 
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 <math>\textnormal{ATIME}(f(n)) \subseteq \textnormal{SPACE}(f(n))</math>,
 
# Jeśli <math>f(n)\geqslant n</math> to <math>\textnormal{SPACE}(f(n)) \subseteq \textnormal{ATIME}(f^2(n))</math>,
 
# Jeśli <math>f(n)\geqslant \textnormal{log}n</math> to <math>\textnormal{ASPACE}(f(n)) \subseteq \textnormal{TIME}(c^{f(n)})</math>.
 
# Jeśli <math>f(n)\geqslant \textnormal{log}n</math> to <math>\textnormal{ASPACE}(f(n)) \supseteq \textnormal{TIME}(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 <math>\textnormal{log}(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},\textnormal{ dla }i>0</math>,
 
* <math>\sum_{i+1} P = NP^{\sum_i P},\textnormal{ dla }i>0</math>,
 
* <math>\prod_{i+1} P = coNP^{\sum_i P},\textnormal{ dla }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ę:
 
====Ćwiczenie====
 
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 <math>\sum_{i+1} P = \sum P</math>.
 
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>.
 
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 <math>\textnormal{QSAT}_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ż:
 
====Ćwiczenie====
 
Pokaż, że jeśli istnieje problem PH-zupełny, to hierarchia zapada się na pewnym poziomie.
 
Zauważ, że problem zupełny musi należeć do konkretnego poziomu.
 
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>.
 
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==
 
====Ćwiczenie====
 
Pokaż, że problem TAUTOLOGY jest coNP-zupełny.
 
Skorzystaj z faktu, że SAT jest NP-zupełny.
 
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.
 
====Ćwiczenie====
 
Udowodnij własności od 1 do 3 z twierdzenia [[##tw:arel|Uzupelnic tw:arel|]].
 
# Jeśli <math>f(n)\geqslant n</math> to <math>\textnormal{ATIME}(f(n)) \subseteq \textnormal{SPACE}(f(n))</math>,
 
# Jeśli <math>f(n)\geqslant n</math> to <math>\textnormal{SPACE}(f(n)) \subseteq \textnormal{ATIME}(f^2(n))</math>,
 
# Jeśli <math>f(n)\geqslant \textnormal{log}n</math> to <math>\textnormal{ASPACE}(f(n)) \subseteq \textnormal{TIME}(c^{f(n)})</math>.
 
<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>
 
<br>
Ad. 1:<br>
Weźmy dowolny język <math>L\in\textnormal{ATIME}(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\textnormal{SPACE}(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 <math>\textnormal{log}(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\textnormal{ASPACE}(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 \textnormal{log}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.
 
====Ćwiczenie====
 
Udowodnij, że problemy TSP(D) i EXACT TSP są wielomianowo równoważne.
 
Skorzystaj z problemu HAMILTON PATH.
 
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).
 
==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”