Test Arka

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{log}(f(n))} $log(f(n))$

Twierdzenie [Uzupelnij]

{{{3}}}

Twierdzenie [Uzupelnij]

(twierdzenie Immermana-Szelepcsényi'ego) Jeśli $f(n)$ jest konstruowalna pamięciowo, to NSPACE(f(n))coNSPACE(f(n)).

Twierdzenie [Uzupelnij]

(twierdzenie Immermana-Szelepcsényi'ego) Jeśli $f(n)$ jest konstruowalna pamięciowo, to $NSPACE(f(n))=coNSPACE(f(n))$.

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(log$n$), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci logarytmicznej,

• Klasa NL = NSPACE(log$n$), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,

• Klasa coNL = coNSPACE(log$n$), 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

Zwróć uwagę na fakt, że problem REACHABILITY jest związany z wykonywaniem obliczeń przez maszynę Turinga.

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 $\varphi$ jak dla problemu SAT.
Wyjście: czy każde wartościowanie spełnia $\varphi$?

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 $\bar{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

Pokaż inkluzje w obie strony korzystając z symetrii klas.

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=L_1\cap L_2$, gdzie $L_1\in NP$ natomiast $L_2\in 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 $\varphi$ i $\psi$ jak dla SAT.
Wyjście: czy formuła $\varphi$ jest spełnialna, natomiast $\psi$ niespełnialna?

Ćwiczenie

{{{3}}}

Wskazówka

Skorzystaj z redukcji języka z NP oraz dopełnienia języka z coNP do SAT.

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 $\varphi$ jak dla SAT.
Wyjście: czy formuła $\varphi$ 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 $(n^k)=\bigcup _{j>0}$ ATIME $(n^j)$, to klasa tych języków, które mogą być akceptowane w alternującym czasie wielomianowym,
• Klasa AL = ASPACE(log$n$), 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

Pokaż że problem coNP-zupełny TAUTOLOGY należy do AP.

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 $\varphi$ jak dla problemu SAT.
Wyjście: czy $\varphi$ jest minimalna, tzn. czy żadna krótsza formuła nie jest jej równoważna?

Ćwiczenie

{{{3}}}

Wskazówka

Wykorzystaj dwa tryby alternacji.

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))\subseteq$ SPACE $(f(n))$,
2. Jeśli $f(n)⩾n$ to SPACE $(f(n))\subseteq$ ATIME $(f^2(n))$,
3. Jeśli $f(n)⩾$ log $n$ to ASPACE $(f(n))\subseteq$ TIME $(c^{f(n)})$.
4. Jeśli $f(n)⩾$ log $n$ to ASPACE $(f(n))\supseteq$ TIME $(c^{f(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 $M^L$. Przypomnijmy, że jest to zwykła maszyna $M$ z dodatkową możliwością zadania pytania postaci "czy $x\in L$?" które kosztuje jedną jednostkę czasu. Rozszerzenie tego pojęcia na klasy jest naturalne. Poprzez $P^{NP}$ 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 $N{P}^{NP}$. 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$:

• $\sum _{0}P=\prod _{0}P={\mathrm{\Delta }}_{0}P=P$
• ${\mathrm{\Delta }}_{i+1}P=P^{\sum _{i}P},$ dla $i>0$,
• $\sum _{i+1}P=N{P}^{\sum _{i}P},$ dla $i>0$,
• $\prod _{i+1}P=coN{P}^{\sum _{i}P},$ dla $i>0$.

Dodatkowo poprzez $PH$ oznaczamy sumę wszystkich tych klas, czyli:
$PH=\bigcup _{i⩾0}\sum _{i}P$.

Ponieważ na poziomie zerowym wszystkie elementy hierarchii to P, więc na poziomie pierwszym, ponieważ taka wyrocznia nic nie daje, otrzymujemy ${\mathrm{\Delta }}_{1}P=P,\sum _{1}P=NP,\prod _{1}P=coNP$. Drugi poziom, to klasy${\mathrm{\Delta }}_{2}P=P^{NP},\sum _{2}P=N{P}^{NP},\prod _{2}P=coN{P}^{NP}$. Warto zwrócić uwagę, że $\prod _{i}P$ jest dopełnieniem $\sum _{i}P$ 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 $\sum _{i}P$ wtedy i tylko wtedy, gdy istnieje wielomianowo zrównoważona i rozstrzygalna relacja $R$ ($i+1$-argumentowa), taka, że $x\in L$ dokładnie wtedy, gdy $\mathrm{\exists }{y}_1\mathrm{\forall }{y}_2\mathrm{\exists }{y}_3\dots Q{y}_i$ takie, że $R(x,y_1,\dots ,y_i)$ 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

Pokaż, że $\sum _{i+1}P=\sum P$.

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 $\varphi$ jak dla problemu SAT poprzedzona $i$ naprzemiennymi grupami kwantyfikatorów egzystencjalnych i uniwersalnych: $\mathrm{\Phi }=\mathrm{\exists }{x}_1\mathrm{\forall }{x}_2\mathrm{\exists }{x}_3\dots Q{x}_i\varphi$.
Wyjście: czy $\mathrm{\Phi }$ jest prawdziwa?

Twierdzenie [Uzupelnij]

Problem $QSA{T}_i$ jest $\sum _{i}P$-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

Zauważ, że problem zupełny musi należeć do konkretnego poziomu.

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\subseteq P^{PP}$, 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

Skorzystaj z faktu, że SAT jest NP-zupełny.

Rozwiązanie

{{{3}}}

Ćwiczenie

{{{3}}}

Wskazówka

Ad. 1 i 3: zasymuluj maszynę alternującą przy pomocy zwykłej.
Ad. 2: skorzystaj z idei zaczerpniętej z twierdzenia Savitcha.

<span id="
Ad. 1:
Weźmy dowolny język $L\in$ ATIME $(f(n))$ akceptowany przez alternującą maszynę Turinga $M$. Dokonamy symulacji przy pomocy deterministycznej maszyny w pamięci $f(n)$. 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 $M$, czyli $f(n)$. Na każdy poziom rekurencji potrzeba nam jednak $f(n)$, aby zapamiętać konfigurację, czyli łącznie $f^2(n)$.

Możemy jednak zaoszczędzić na pamięci pamiętając tylko który z niedeterministycznych wyborów dokonała $M$ 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 $f(n)$, stąd cała symulacja potrzebuje $f(n)$ pamięci, a więc $L\in$ SPACE $(f(n))$.

Ad. 2:
Tym razem mamy do dyspozycji maszynę działającą w pamięci $f(n)$ i chcemy ją zasymulować przy pomocy maszyny alternującej w czasie $f^2(n)$. Jak w twierdzeniu Savitcha odwołamy się do grafu konfiguracji maszyny rozmiaru $c^{f(n)}$ 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 $n$ ma do dyspozycji alternację i dokonuje tego w dwóch etapach. W pierwszym zgaduje wierzchołek pośredni $t$ 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 $n/2$ poprzez odgadnięty wierzchołek $t$ istnieją.

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

Ad. 3:
Weźmy dowolny język $L\in$ ASPACE $(f(n))$ akceptowany przez alternującą maszynę Turinga $M$. Mamy do dyspozycji czas rzędu wykładniczego względem $f(n)$, a więc możemy wygenerować cały graf konfiguracji obliczeń maszyny $M$ (który jak wiemy ma rozmiar $c^{f(n)}$, gdy $f(n)⩾$ log $n$). Następnie stosownie do typów "AND" i "OR" przeglądamy graf od konfiguracji końcowych i decydujemy o akceptacji słowa wejściowego. " style="font-variant:small-caps">Rozwiązanie

{{{3}}}

Ćwiczenie

{{{3}}}

Wskazówka

Skorzystaj z problemu HAMILTON PATH.

Rozwiązanie

{{{3}}}