Złożoność obliczeniowa/Wykład 14: Pamięć wielomianowa i złożoność wykładnicza: Różnice pomiędzy wersjami

Aktualna wersja na dzień 11:11, 5 wrz 2023

Klasa PSPACE

W tym module zajmiemy się klasą PSPACE, która, przypomnijmy, jest klasą tych języków, które są akceptowane przez maszynę deterministyczną w pamięci wielomianowej.

Na podstawie twierdzenia Savitcha wiemy jednak, że jest ona równa klasie NPSPACE, czyli języków, które są akceptowane przez maszynę niedeterministyczną w pamięci wielomianowej.

Klasa PSPACE posiada wiele naturalnych problemów zupełnych, które omawiamy w następnej części. Zupełność definiujemy przy pomocy wielomianowej redukcji jak w poprzednich rozdziałach.

Problemy PSPACE-zupełne

Najbardziej naturalny i pierwszy problem PSPACE-zupełny, który zdefiniujemy wywodzi się oczywiście z SAT:

Definicja 2.1 [Problem $QSAT$ ]

Wejście: formuła logiczna $ϕ$ jak dla problemu SAT poprzedzona dowolną liczbą naprzemiennych kwantyfikatorów: $Φ = \exists x_{1} \forall x_{2} \exists x_{3} \dots Q x_{k} ϕ$ .
Wyjście: czy $Φ$ jest prawdziwa?

Przypomnijmy, że na użytek hierarchii wielomianowej definiowaliśmy problem ${QSAT}_{i}$ , który mógł mieć $i$ naprzemiennych kwantyfikatorów, natomiast tutaj może być ich dowolna ilość. Fakt, że kwantyfikatory muszą występować na zmianę nie jest istotnym ograniczeniem, gdyż można kwantyfikować po zmiennych, które w formule nie występują. Problem ten w literaturze pojawia się też jako QBF (ang. Quantified Boolean Formula).

Twierdzenie 2.2

Problem $QSAT$ jest PSPACE-zupełny.

Dowód

{{{3}}}

Oto przykład dwóch innych problemów, których będziemy używać w dalszej części. Ich PSPACE-zupełność jest przedmiotem ćwiczenia końcowego:

Definicja 2.3 [Problem IN PLACE ACCEPTANCE (akceptacja w miejscu)]

Wejście: maszyna M i słowo $x$
Wyjście: czy maszyna M akceptuje słowo $x$ używając $| x |$ pamięci?

Definicja 2.4 [Problem IN PLACE DIVERGENCE (rozbieżność w miejscu)]

Wejście: maszyna M
Wyjście: czy maszyna M pętli się używając $| M |$ pamięci?

Optymalizacja periodyczna

Graf periodyczny.

Wśród problemów PSPACE-zupełnych znajdują się wersje periodyczne (inaczej okresowe) znanych problemów. Jako pierwszy rozważmy problem PERIODIC GRAPH COLORING. Polega on na kolorowaniu grafu periodycznego. Poniższy przykład powinien wszystko wyjaśnić:

W animacji Graf periodyczny widać nieskończony graf periodyczny i jego skończony zwięzły zapis. Krawędź oznaczona etykietą $+ 1$ oznacza, że następuje połączenie pomiędzy wierzchołkami z grup odległych o 1. W takim zapisie możemy stosować również etykiety oznaczone większymi liczbami oraz liczbami ujemnymi.

Naszym zadaniem jest obliczenie liczby chromatycznej grafu periodycznego lub stwierdzenie czy jest mniejsza niż $k$ dla wersji decyzyjnej. Dla powyższego grafu wynosi ona 2, mimo, iż graf jest nieskończony!

Podobnie można przedstawić problem PERIODIC SAT. Tym razem formuła jest nieskończona i periodyczna, natomiast w jej zwięzłym zapisie możemy stosować klauzule postaci $x \lor y_{+ 1} \lor \neg z$ , w których $+ 1$ oznacza powiązanie pomiędzy zmiennymi z sąsiednich grup. Podobnie jak w normalnym SAT pytamy o istnienie wartościowania spełniającego.

Analizowanie przedstawionych powyżej nieskończonych struktur może wydawać się zadaniem niewykonalnym, jednakże oba powyższe problemy okazują się być PSPACE-zupełne.

Ćwiczenie 2.5

Udowodnij, że problem PERIODIC SAT jest PSPACE-zupełny.

Wskazówka

Rozwiązanie

Pokażmy najpierw że PERIODIC SAT należy do PSPACE. Załóżmy, że wartościowanie spełniające istnieje. Jest to nieskończony ciąg wartościowań grup zmiennych

\dots, X_{i}, X_{i + 1}, \dots

. Rozmiary

X_{i}

odpowiadają zapisowi pojedynczej grupy zmiennych przedstawionym na wejściu (rozmiaru

n

).

Łatwo zauważyć, że sąsiednie grupy mogą być wartościowane na $2^{2 n}$ sposobów, stąd spełniające wartościowanie nieskończone posiada okres o długości co najwyżej tego rzędu, gdyż powtórzy się w nim ta sama para wartościowań sąsiednich grup zmiennych. To pozwala nam przejść od analizy formuł nieskończonych do tych o wykładniczej ilości grup zmiennych.

Wykorzystując maszynę niedeterministyczną zgadujemy wartościowanie wykładniczej długości dla kolejnych grup zmiennych $T_{i}$ (w tej samej pamięci) sprawdzając na każdym etapie, czy jest spełniające w ramach grupy i odpowiedni fragment w przód i w tył na podstawie uogólnionych klauzul. Na podstawie równości NPSPACE i PSPACE otrzymujemy potrzebny algorytm.

Teraz pokażmy zupełność problemu. Zredukujemy wspomniany PSPACE-zupełny problem IN PLACE DIVERGENCE do PERIODIC SAT.

Bierzemy maszynę M i pytamy czy istnieje dla niej obliczenie nieskończone w miejscu. Kodujemy konfigurację maszyny w pojedynczej grupie zmiennych z problemu PERIODIC SAT. Wzorujemy się na dowodzie twierdzenia Cooka-Levina. Poprawne przejścia pomiędzy konfiguracjami kodujemy przy pomocy uogólnionych klauzul. Jeśli skonstruowana w taki sposób formuła periodyczna jest spełnialna, to w jednoznaczny sposób odpowiada to obliczeniu nieskończonemu maszyny w miejscu.

Gry

Okazuje się, że klasa PSPACE to miejsce w którym zadomowiła się grupa problemów opartych na grach. Dzieje się tak dlatego, iż QSAT może w pewnej interpretacji obrazować grę dwuosobową. Kwantyfikator egzystencjalny odpowiada ruchowi gracza, który wybiera jedną z możliwości. Kwantyfikator uniwersalny odpowiada dowolnej odpowiedzi drugiego gracza. Strategia wygrywająca to taki algorytm, który pozwala wygrać pierwszemu graczowi, niezależnie od ruchów podjętych przez drugiego.

Rozważmy grę dwuosobową powiązaną z formułą QSAT która polega na znalezieniu wartościowania spełniającego dla zmiennych przez pierwszego gracza (drugi stara się mu w tym przeszkodzić). Kolejne ruchy graczy to wybory wartości dla zmiennych $x_{1}, \dots, x_{k}$ . Na końcu następuje sprawdzenie prawdziwości formuły bez kwantyfikatorów.

Zdefiniujmy następujący problem:

Definicja 3.1 [Problem FORMULA GAME]

Wejście: formuła $Φ$ jak dla QSAT
Wyjście: czy gracz I ma strategię wygrywającą dla $Φ$ ?

Ćwiczenie 3.2

Udowodnij, że FORMULA GAME jest problemem PSPACE-zupełnym.

Wskazówka

Rozwiązanie

Po tak szeroko skomentowanej odpowiedniości pomiędzy QSAT i FORMULA GAME redukcja jest dosyć oczywista. Istnienie strategii może zostać sprawdzone w pamięci wielomianowej poprzez sprawdzenie wszystkich wartościowań stosownie do reguł gry, zupełnie tak jak działo się w dowodzie, że QSAT należy do PSPACE.

Teraz redukcja QSAT do FORMULA GAME. Opiera się ona na własności strategii wygrywającej. Rozważmy $Φ = \exists x_{1} \forall x_{2} \exists x_{3} \dots Q x_{k} ϕ$ . Gdy posiadamy strategię wygrywającą, to istnieje taki wybór $x_{1}$ , który sprawia, że osiągniemy sukces. Taką dokładnie wartość wybieramy dla $x_{1}$ kwantyfikowanej egzystencjalnie. Następnie gracz II wykonuje dowolny ruch, lecz w naszej strategii jesteśmy na to przygotowani - tym samym $ϕ$ będzie prawdziwa, przy dowolnym wartościowaniu $x_{2}$ itd. Ostatecznie formuła $Φ$ jest prawdziwa wtedy i tylko wtedy, gdy istnieje strategia wygrywająca dla FORMULA GAME. Nasza redukcja jest zupełnie przezroczysta - przepisuje formułę $Φ$ bezpośrednio.

Gra GEOGRAPHY.

Następnym obrazowym dla nas przykładem będzie dwuosobowa gra GEOGRAPHY, znana ze świata rzeczywistego, polegająca na kolejnym wypowiadaniu przez graczy nazw miast w ten sposób, aby każde kolejne zaczynało się na taką literą na jaką kończy się poprzednie. Nie można używać miast wielokrotnie. Przegrywa ten, kto nie może wykonać ruchu. Animacja Gra GEOGRAPHY obrazuje fragment planszy gry i możliwe przejścia w formie grafu.

Aby zanalizować złożoność obliczeniową musimy dokonać pewnych technicznych zabiegów. Przede wszystkim dopuścimy dowolnie duże plansze (co już nie odpowiada rzeczywistości) oraz przekształcimy problem do postaci decyzyjnej:

Definicja 3.3 [Problem GEOGRAPHY]

Wejście: Graf G i wierzchołek początkowy x
Wyjście: Czy gracz I ma strategię wygrywającą?

Twierdzenie 3.4

GEOGRAPHY jest problemem PSPACE-zupełnym.

Redukcja QSAT do GEOGRAPHY.

Dowód

Najpierw pokażmy, że GEOGRAPHY należy do PSPACE. Argument jest zupełnie podobny do tego spotkanego w QSAT. Konstruujemy algorytm rekurencyjny, który przegląda wszystkie możliwe przebiegi rozgrywki i stosownie odpowiada na pytanie. Korzystamy tutaj z odpowiedniości pomiędzy kwantyfikatorem egzystencjalnym i ruchem pierwszego gracza, oraz kwantyfikatorem uniwersalnym i ruchem drugiego gracza w analizie strategii wygrywającej. Ponieważ liczba ruchów jest ograniczona przez liczbę wierzchołków G zatem taka symulacja może odbyć się w pamięci wielomianowej.

Następnie zredukujemy problem QSAT do GEOGRAPHY. Weźmy dowolną formułę $Φ$ i przekształćmy ją w planszę do GEOGRAPHY. Przykład postępowania dla $Φ = \exists x \forall y \exists z ((\neg x \lor \neg y) \land (y \lor z) \land (y \lor \neg z))$ przedstawiony jest w animacji Redukcja QSAT do GEOGRAPHY.:

Konstrukcja jest dosyć prosta. Najpierw występuje ciąg rombów odpowiadający wartościowaniu zmiennych formuły. Zwróćmy uwagę, że plansza jest tak skonstruowana, iż wartości dla kolejnych zmiennych są wybierane przez graczy na zmianę. Tym samym gracz I ustala wartości zmiennych kwantyfikowanych egzystencjalnie, a gracz II uniwersalnie. Gdy gra dochodzi do dolnej części animacji to gracz II (bez straty ogólności zakładamy, że zmiennych jest nieparzysta ilość) wybiera wyjście odpowiadające klauzuli (w naszej interpretacji wybiera klauzulę niespełnioną). Następnie gracz I wykonuje ruch, który jest możliwy wtedy i tylko wtedy, gdy w klauzuli istnieje literał spełniony. Gracz II nie ma wtedy kolejnego ruchu.

Pokazaliśmy tym samym równoważność strategii wygrywającej dla gracza I i prawdziwości formuły QSAT.

Okazuje się, że jednym z ważniejszych elementów gry dwuosobowej, który powoduje, że należy ona do PSPACE, jest wielomianowe ograniczenie liczby możliwych ruchów (w tym wypadku rozmiar planszy). Podobnie stanie się gdy uogólnimy znaną dwuosobową grę planszową GO na dowolnie duże plansze. Również ona okazuje się PSPACE-zupełna.

Przy szachach natomiast napotykamy na problem innego rodzaju. Gra ta nie poddaje się zastosowanej analizie złożoności, gdyż jej uogólnienie na dowolne plansze traci istotne wewnętrzne cechy tradycyjnej rozgrywki. W ten sposób sama gra z punktu widzenia złożoności ma rozmiar stały i wymyka się naszym metodom.

Złożoność wykładnicza

Ze względu na twierdzenia o hierarchii czasowej i pamięciowej wiemy, że rozważana w poprzednim rozdziale klasa PSPACE oczywiście nie obejmuje wszystkich języków. Naturalnym krokiem jest rozważanie klas o złożoności wykładniczej, które definiowaliśmy już wcześniej:

Klasa EXPSPACE = SPACE( $2^{n^{k}}$ ), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wykładniczej,

Klasa NEXPSPACE = NSPACE( $2^{n^{k}}$ ), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wykładniczej.

Klasa EXP = TIME( $2^{n^{k}}$ ), to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wykładniczym,

Klasa NEXP = NTIME( $2^{n^{k}}$ ), to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wykładniczym.

Na tym wykładniczym poziomie złożoności występuje wiele podobieństwa do wielomianowych klas. Ponownie na mocy twierdzenia Savitcha wiemy, że EXPSPACE = NEXPSPACE. Wiemy także, że

P S P A C E \subseteq E X P \subseteq N E X P \subseteq E X P S A C E

co w połączeniu z faktem z twierdzenia hierarchii, że PSPACE zawiera się ściśle w EXPSPACE daje nam, że przynajmniej jedna z powyższych trzech nierówności jest ścisła, choć nie wiemy która.

Podobnie:

P \subseteq N P \subseteq P S P A C E \subseteq E X P

oraz wiemy, że P zawiera się ściśle w EXP, na podstawie twierdzenia o hierarchii czasowej. Stąd ponownie jedna z trzech nierówności musi być ścisła, choć nie wiemy która. Prawdopodobnie wszystkie. Najważniejsze pytanie, to czy EXP=NEXP?

Mimo tej niewiedzy możemy udowodnić ciekawy fakt łączący hipotezy występujące na dwóch wspomnianych poziomach:

Ćwiczenie 4.1

Udowodnij, że jeżeli P=NP to EXP=NEXP.

Wskazówka

Rozwiązanie

Weźmy dowolny język L z NEXP i pokażmy, dzięki równości NP i P, że należy on do EXP.

Załóżmy, że L jest akceptowany przez maszynę niedeterministyczną N w czasie $2^{n^{k}}$ . Wprowadzimy teraz język $L^{'}$ , które powstaje na podstawie L:

L^{'} = {x #'^{2^{| x |^{k}} - | x |} : x \in L}

czyli innymi słowy wszystkie słowa z L, lecz unormowane do odpowiedniej długości przy użyciu quasi-blanków (jak gdyby pustych, ale odróżnialnych przez nas od pustych).

Okazuje się, że język $L^{'}$ należy teraz do NP. Maszyna N', która tego dokonuje sprawdza, czy słowo ma odpowiednią długość, a następnie symuluje działanie N. Dzięki wykładniczym "rozdmuchaniu" słowa wejściowego maszyna N' ma złożoność wielomianową względem rozmiaru danych (nawet liniową).

Na podstawie założenia P=NP wiemy, że istnieje wielomianowa maszyna deterministyczna M', która akceptuje $L^{'}$ w czasie $n^{l}$ . Teraz dokonujemy przekształcenia w odwrotnym kierunku, otrzymując maszynę deterministyczną M, która akceptuje L w deterministycznym czasie wykładniczym $2^{n^{l}}$ , co pokazuje, że L należy do EXP.

Konstrukcja M to symulacja maszyny M' na słowie wejściowym. Bez straty ogólności można założyć, że maszyna traktuje taśmę wejściową jako tylko do odczytu. W tej sytuacji musimy tylko pamiętać pozycję w ciągu quasi-blanków, co nie przedstawia trudności.

W tej sytuacji pokazanie, że EXP $\neq$ NEXP implikuje, że P $\neq$ NP, więc jest teoretycznie trudniejszym faktem.

Wnioski z powyższego ćwiczenia są dalej idące. Możemy mianowicie wywnioskować, że nierówność stosownych klas złożoności przenosi się w dół, natomiast równość w górę:

Wniosek 4.2

Jeśli $g (n) ⩾ n$ i $f (n)$ są konstruowalne czasowo, to $TIME (f (n)) = NTIME (f (n)) \Rightarrow TIME (g (f (n))) = NTIME (g (f (n)))$

Hierarchia klas złożoności.

Wszystkie wspomniane klasy złożoności wykładniczej posiadają problemy zupełne. Co warte podkreślenia, na podstawie twierdzeń o hierarchii czasowej klasa EXP nie może kolapsować do P, więc problemy EXP-zupełne nie mają rozwiązania wielomianowego, czyli nie należą do P!

Podobnie, problemy EXPSPACE-zupełne nie należą do PSPACE, a zatem nie należą także do NP! To jednak dosyć trudna metoda wykazywania, że problem nie należy do NP.

Na podstawie twierdzeń o hierarchii wiemy, że możemy wyróżnić coraz trudniejsze problemy i coraz większe (istotnie większe) klasy. Przykładem są klasy złożoności podwójnie wykładniczej 2EXP i 2NEXP, o których ponownie nie wiemy czy są równe.

Jedną z ciekawych klas jest ELEMENTARY, która jest sumą klas:

T I M E (2^{2^{⋮^{2^{n^{k}}}}})

i nazywamy ją klasą języków elementarnych. Są jednak problemy, które i do tej klasy nie należą. Największą klasą przedstawioną w animacji Hierarchia klas złożoności obrazującym zależności pomiędzy poznanymi klasami złożoności jest R - klasa wszystkich języków rozstrzygalnych.

Problemy zwięzłe

W tej części omówimy krótko zabieg podobny do problemów periodycznych omawianych w poprzedniej części. Ponownie wprowadza on całą klasę problemów analogicznych do klasycznych takich jak SAT, czy HAMILTONIAN PATH. Problemy zwięzłe (ang. SUCCINCT) są to wersje problemów, w których wejście jest zapisane w sposób bardzo zwięzły i przez ten fakt, złożoność działania algorytmów przenosi się na wyższy poziom.

Zwięzła reprezentacja grafu $G$ o $n = 2^{b}$ wierzchołkach oznaczana przez $G_{C}$ to sieć logiczna $C$ o $2 b$ wejściach. Gdy podamy jej na wejściu $i$ i $j$ zakodowane binarnie to otrzymamy jako wynik odpowiedź na pytanie czy $i$ jest połączone z $j$ w grafie $G$ .

Gdy przedstawimy graf wejściowy w formie zwięzłej dla HAMILTONIAN PATH (który jest problemem NP-zupełnym), to otrzymamy SUCCINCT HAMILTONIAN PATH, który będzie NEXP-zupełny poprzez zastosowanie tego samego algorytmu. Podobnie będzie w przypadku innych problemów grafowych.

Możliwe jest również zwięzłe przedstawienie formuł i sieci logicznych. W ten sposób możemy otrzymać problemy SUCCINCT CIRCUIT VALUE i SUCCINCT CIRCUIT SAT, które są odpowiednio EXP-zupełne i NEXP-zupełne.

Wyrażenia regularne

Ciekawym polem do analizy złożoności jest standardowy język wyrażeń regularnych, w których możemy używać symboli konkatenacji, sumy zbiorów oraz $⋆$ :

Definicja 4.3 [Problem $E Q_{R E X}$ ]

Wejście: Wyrażenia regularne R i S
Wyjście: Czy R i S są równoważne (opisują ten sam język)?

Powyższy problem jest PSPACE-zupełny. Jeśli jednak dopuścimy dodatkowy symbol $↑$ - operację potęgowania, która działa następująco:

R^{k} = R ↑ k = \overset{k}{\overset{⏞}{R \circ R \circ \dots \circ R}}

to otrzymujemy uogólnione wyrażenia regularne. Co ciekawe, takie rozszerzenie zmienia tylko zapis, gdyż każdą operację potęgowania można zamienić na stosowną liczbę operacji konkatenacji. Zakładamy, że $k$ jest zapisane binarnie.

Definicja 4.4 [Problem $E Q_{R E X ↑}$ ]

Wejście: Wyrażenia regularne R i S z operacją potęgowania
Wyjście: Czy R i S są równoważne?

Twierdzenie 4.5

Problem $E Q_{R E X ↑}$ jest problemem EXPSPACE-zupełnym.

Dowód

Pierwsza część dowodu to jak zwykle pokazanie przynależności problemu do klasy EXPSPACE. Eliminujemy nową operację potęgowania tak jak opisano to powyżej. Zwróćmy uwagę, że w wyniku tego procesu wyrażenia rosną wykładniczo. Następnie konstruujemy niedeterministyczne automaty skończone do rozpoznawania wyrażeń regularnych R i S oraz sprawdzamy ich równoważność. Ten proces może zostać wykonany w EXPSPACE w sposób następujący:

Najpierw skonstruujemy niedeterministyczny algorytm, który sprawdza czy dwa automaty nie są równoważne, działający w czasie liniowym. Na podstawie twierdzenia Savitcha otrzymamy algorytm deterministyczny działający w czasie kwadratowym, a stąd otrzymamy algorytm deterministyczny sprawdzający czy automaty są równoważne.

Niedeterministyczny algorytm sprawdzający nierównoważność automatów dokonuje równoległej symulacji na słowach wykładniczej długości względem ich rozmiarów (bo jeśli są różne to na takiej długości słowie). Gdy stwierdzi, że automaty dają różną odpowiedź to akceptuje.

Do drugiej części dowodu potrzebne nam będzie pojęcie historii obliczeń maszyny Turinga. Jest to ciąg konfiguracji $C_{1}, \dots, C_{k}$ maszyny M, które przechodzi ona kolejno podczas obliczeń na słowie wejściowym $x$ . Ostatnia konfiguracja jest akceptująca bądź odrzucająca. Możemy zapisać historię obliczeń w formie następującego słowa:

# C_{1} # \dots # C_{k} #

gdzie $C_{i}$ stanowią pełny zapis konfiguracji maszyny.

Weźmy dowolny język L z EXPSPACE akceptowany przez maszynę M działającą w czasie $2^{n^{k}}$ . Dla słowa $x$ skonstruujemy wyrażenia regularne R i S, które są równoważne wtedy i tylko wtedy, gdy M akceptuje $x$ . Idea jest bardzo prosta. R będzie generować wszystkie słowa, które zawierają symbole z dowolnej historii obliczenia maszyny M na $x$ . Wyrażenie S natomiast, będzie generować wszystkie słowa, które nie są odrzucającymi historiami obliczeń. Jeśli R i S okażą się równoważne, to znaczy, że $x \in L$ .

Przenieśliśmy ciężar dowodu na konstrukcję stosownych wyrażeń regularnych, które muszą generować gigantycznej długości słowa. Wyrażenie R jest bardzo proste, gdyż ma za zadanie wygenerować wszystkie słowa nad alfabetem ${# \cup Q \cup Γ}$ , czyli $R = {# \cup Q \cup Γ}^{⋆}$ .

Wyrażenie Q musi natomiast pominąć słowa opisujące historie obliczeń M odrzucające $x$ . Słowo takie może nie kodować odrzucającej historii obliczeń, jeśli jego początkowa lub końcowa konfiguracja jest zła, bądź w środku nie zachowuje się poprawnie. Przyjmujemy założenie, że wszystkie konfiguracje są wypełnione do prawej strony symbolami pustymi do długości $2^{n^{k}}$ . Oznaczmy zatem przez $Q = Q_{1} \cup Q_{2} \cup Q_{3}$ wyrażenie regularne zawierające trzy stosowne części.

Teraz następuje część najbardziej techniczna. Trzeba opisać wyrażeniem regularnym wszystkie możliwe nieprawidłowe podsłowa. Jest to możliwe do wykonania przy pomocy wyrażenia wielomianowej wielkości. Z pomocą przyjdzie wprowadzona operacja $↑$ . Nie przedstawiamy tutaj szczegółów technicznych, a do pełnej konstrukcji odsyłamy do literatury.

Co fascynujące, gdy dodamy kolejną operację do naszych wyrażeń regularnych - negację zbioru, to okazuje się, że problem równoważności tak uogólnionych wyrażeń regularnych przestaje być elementarny!

Ćwiczenia dodatkowe

Ćwiczenie 5.1

Udowodnij, że problemy IN PLACE ACCEPTANCE i IN PLACE DIVERGENCE są PSPACE-zupełne.

Wskazówka

Rozważ instancję problemu IN PLACE ACCEPTANCE, w którym

x

ma na końcu dopisane blanki (). Sprowadź IN PLACE ACCEPTANCE do IN PLACE DIVERGENCE.

Rozwiązanie

Najpierw pokażmy, że IN PLACE ACCEPTANCE należy do PSPACE. Symulacja działania maszyny w pamięci

| x |

, czyli liniowej, jest jednak łatwa. Dodatkowo używamy licznika, który zlicza kroki maszyny (rzędu

c^{| x |}

, czyli liczby konfiguracji) aby wykryć zapętlenie.

Weźmy teraz dowolny język L z PSPACE. Jest on akceptowany przez maszynę M w pamięci $n^{k}$ . Oczywistym jest, że M akceptuje $x$ wtedy i tylko wtedy, gdy akceptuje $x #^{n^{k}}$ w miejscu, bo dopisanie dowolnej liczby blanków na końcu słowa wejściowego nie ma żadnego znaczenia. Ponieważ dodatkowe blanki liczą się teraz do rozmiaru $x$ , to maszyna akceptuje słowo w miejscu.

Problem IN PLACE ACCEPTANCE zredukujemy do IN PLACE DIVERGENCE tak jak to zapowiedziano we wskazówce, pokazując tym samym PSPACE-zupełności tego ostatniego.

Rozważmy wejście w postaci maszyny M i słowa x. Konstruujemy maszynę $M^{'}$ która rozpoczyna działanie od zapisania słowa $x$ na taśmie, a następnie symuluje M zliczając jej kroki. Na końcu występuje faza przekątniowa. Gdy $M$ akceptuje to $M^{'}$ przechodzi do początkowej konfiguracji i tym samym wpada w nieskończone obliczenie. Gdy $M$ przekracza dozwoloną liczbę kroków (ograniczoną, gdyż maszyna działa w miejscu), to $M^{'}$ akceptuje.

Teraz pozostaje zauważyć, że maszyna $M^{'}$ ma nieskończone obliczenie wtedy i tylko wtedy gdy $M$ akceptuje słowo $x$ w miejscu.

Ćwiczenie 5.2

Pokaż że jeśli $g (n) ⩾ n$ i $f (n)$ są konstruowalne pamięciowo, to $SPACE (f (n)) = NSPACE (f (n)) \Rightarrow SPACE (g (f (n))) = NSPACE (g (f (n)))$ .

Wskazówka

Rozwiązanie

Zgodnie ze wskazówką weźmy dowolny język L z klasy

NSPACE (g (f (n)))

. Weźmy maszynę niedeterministyczną N

działającą w pamięci $g (f (n))$ . Wprowadzamy język:

L^{'} = {x #'^{f^{- 1} (g (f (| x |))) - | x |} : x \in L}

gdzie $#^{'}$ oznacza quasi-blanki.

Okazuje się, że język $L^{'}$ należy teraz do $SPACE (f (n))$ . Maszyna N', która tego dokonuje sprawdza, czy słowo ma odpowiednią długość, a następnie symuluje działanie N. Dzięki "rozdmuchaniu" słowa wejściowego maszyna N' ma złożoność $f (n)$ .

Ponownie na podstawie założenia $SPACE (f (n)) = NSPACE (f (n))$ wiemy, że istnieje maszyna deterministyczna M' która akceptuje $L^{'}$ w pamięci $f (n)$ . Teraz dokonujemy przekształcenia w odwrotnym kierunku, otrzymując maszynę deterministyczną M, która akceptuje L w deterministycznej pamięci $g (f (n))$ , co pokazuje, że L należy do $SPACE (g (f (n)))$ .

Uzasadnienie jest dokładnie takie samo. Maszyna M symuluje działanie maszyny M' na słowie wejściowym traktowanym jako tylko do odczytu. Jak poprzednio musimy pamiętać pozycję w ciągu quasi-blanków.

Złożoność obliczeniowa/Wykład 14: Pamięć wielomianowa i złożoność wykładnicza: Różnice pomiędzy wersjami

Aktualna wersja na dzień 11:11, 5 wrz 2023

Spis treści

Klasa PSPACE

Problemy PSPACE-zupełne

Optymalizacja periodyczna

Gry

Złożoność wykładnicza

Problemy zwięzłe

Wyrażenia regularne

Ćwiczenia dodatkowe

Testy końcowe

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-= Alternacje i gry
+==Klasa PSPACE==
-= Hierarchia wielomianowa =
+W tym module zajmiemy się klasą PSPACE, która, przypomnijmy, jest klasą tych języków, które są akceptowane przez maszynę deterministyczną w pamięci wielomianowej.
-= Alternacje i gry
+Na podstawie twierdzenia Savitcha wiemy jednak, że jest ona równa klasie NPSPACE, czyli języków, które są akceptowane przez maszynę niedeterministyczną w pamięci wielomianowej.
+Klasa PSPACE posiada wiele naturalnych problemów zupełnych, które omawiamy w następnej części. Zupełność definiujemy przy pomocy wielomianowej redukcji jak w poprzednich rozdziałach.
+==Problemy PSPACE-zupełne==
+Najbardziej naturalny i pierwszy problem PSPACE-zupełny, który zdefiniujemy wywodzi się oczywiście z SAT:
+{{definicja|2.1 [Problem <math>\text{QSAT}</math>]|def 2.1|
+Wejście: formuła logiczna <math>\phi</math> jak dla problemu SAT poprzedzona
+dowolną liczbą naprzemiennych kwantyfikatorów: <math>\Phi=\exists{x_1}\forall{x_2}\exists{x_3}\ldots Q{x_k}\phi</math>.<br>
+Wyjście: czy <math>\Phi</math> jest prawdziwa?
+}}
+Przypomnijmy, że na użytek hierarchii wielomianowej definiowaliśmy problem <math>\text{QSAT}_i</math>, który mógł mieć <math>i</math> naprzemiennych
+kwantyfikatorów, natomiast tutaj może być ich dowolna ilość. Fakt, że kwantyfikatory muszą występować na zmianę nie jest istotnym ograniczeniem, gdyż można kwantyfikować po zmiennych, które w formule nie występują. Problem ten w literaturze pojawia się też jako QBF (ang. Quantified Boolean Formula).
+{{twierdzenie|2.2|tw 2.2|
+Problem <math>\text{QSAT}</math> jest PSPACE-zupełny.
+}}
+{{dowod|||
+W pierwszym kroku pokażmy, że QSAT należy do PSPACE. Weźmy dowolną formułę <math>\Phi=\exists{x_1}\forall{x_2}\exists{x_3}\ldots Q{x_k}\phi</math>.
+Skonstruujemy algorytm rekurencyjny rozwiązujący powyższy problem. Podstawa rekurencji to sytuacja, w której <math>\Phi</math> nie zawiera kwantyfikatorów. W takiej sytuacji zakładamy, że wszystkie zmienne są uniwersalnie skwantyfikowane i sprawdzamy czy formuła jest prawdziwa poprzez rozważenie wszystkich możliwych wartościowań (po kolei w tej samej pamięci).
+Teraz rozważmy <math>\Phi=\exists{x}\Phi'</math>. W tej sytuacji przeglądamy możliwe wartościowania dla <math>x</math>. Ustalamy najpierw <math>x=0</math> i rozważamy formułę <math>\Phi'</math> z tak ustalonym <math>x</math>. Wywołujemy algorytm rekurencyjnie. Jeśli <math>\Phi'</math> okazuje się prawdziwa to i <math>\Phi</math> jest prawdziwa. W przeciwnym wypadku rozważamy <math>x=1</math>.
+Analogicznie dzieje się, gdy <math>\Phi=\forall{x}\Phi'</math>. Tym razem dla obu wartościowań <math>x</math> formuła <math>\Phi'</math> musi być prawdziwa (co ponownie sprawdzamy w sposób rekurencyjny), aby <math>\Phi</math> była prawdziwa. Cały algorytm działa w pamięci wielomianowej, bo głębokość rekurencji jest liniowa.
+Następnie pokażmy, że każdy problem z klasy PSPACE redukuje się do QSAT. Posłużymy się ideą podobną do tej z twierdzenia Savitcha, tzn. rozważmy osiągalność w grafie konfiguracji maszyny.
+Weźmy dowolny język L z klasy PSPACE. Jest on akceptowany przez maszynę M działającą w pamięci wielomianowej. Chcemy na podstawie maszyny M i słowa <math>x</math> zbudować formułę <math>\Phi</math>, która będzie prawdziwa wtedy i tylko wtedy, gdy <math>x\in L</math>.
+Przypomnijmy, że <math>x\in L</math> wtedy i tylko wtedy, gdy istnieje ścieżka od konfiguracji początkowej do końcowej w grafie konfiguracji. Oznaczmy <math>|x|=n</math>. Każda konfiguracja ma rozmiar wielomianowy ze względu na <math>n</math>, zatem wszystkich konfiguracji jest rzędu <math>c^{n^k}</math>.
+Naszym zadaniem jest zbudowanie formuły <math>PATH_i(x,y)</math>, która będzie prawdziwa wtedy i tylko wtedy, gdy istnieje ścieżka od konfiguracji <math>x</math> do <math>y</math> zawierająca co najwyżej <math>2^i</math> wierzchołków. W naszej sytuacji logarytm długości ścieżki jest rzędu <math>n^k</math>. Odpowiedź na pytanie czy słowo należy do L otrzymamy rozważając prawdziwość <math>PATH_{n^k}(start,accept)</math>, gdzie <math>start</math> oznacza konfigurację początkową, a <math>accept</math> akceptującą.
+Będziemy budować formułę <math>PATH_i(x,y)</math>, w której <math>\phi</math> jest w dysjunktywnej postaci normalnej (alternatywy implikantów), a nie koniunktywnej postaci (koniunkcji alternatyw) jak wymaga tego SAT. Takie podejście jest technicznie łatwiejsze, natomiast pod koniec dowodu wyjaśnimy jak sobie z tym poradzić.
+Konfiguracje <math>x</math> i <math>y</math> będziemy reprezentować poprzez <math>n^k</math> zmiennych binarnych. Na początku skonstruujemy <math>PATH_0(x,y)</math>. Nasza formuła musi kodować sytuację <math>x=y</math> lub <math>y</math> osiągalne z <math>x</math> przez M w jednym kroku. W dysjunktywnej postaci normalnej jest to możliwe do zakodowania przy użyciu <math>n^k</math> implikantów.
+Teraz konstruujemy <math>PATH_{i+1}(x,y)</math> przy pomocy <math>PATH_i(x,y)</math>. Intuicyjnie można to zrobić następująco:
+<center><math>PATH_{i+1}(x,y)=\exists{t}PATH_i(x,t)\wedge PATH_i(t,y)</math></center>
+gdzie <math>t</math> to konfiguracja pośrednia kodowana przez nowy komplet <math>n^k</math> zmiennych. Niestety postępując w ten prosty sposób rozmiar ostatecznej formuły będzie wykładniczy, gdyż na każdym poziomie formuła przyrasta dwukrotnie.
+Rozwiążemy ten problem używając jednej kopii formuły <math>PATH_i(x,y)</math>.
+Ten sprytny zabieg przedstawia się następująco:
+<center><math>PATH_{i+1}(x,y)=\exists{t}\forall{p}\forall{q}(((x=p\wedge
+t=q)\vee(t=p\wedge y=q))\Rightarrow PATH_i(p,q)</math></center>
+gdzie <math>t,p,q</math> to stosowne komplety <math>n^k</math> używanych do zapisu konfiguracji. Używamy dwukrotnie formuły <math>PATH_i</math> co odpowiada w pewnym sensie pracy w tej samej pamięci. Łatwo sprawdzić, że powyższa formuła koduje to samo, co wykładnicza formuła przedstawiona wcześniej, jednak nad jej postacią musimy jeszcze popracować.
+Pierwszy ruch to przesunięcie kwantyfikatorów z <math>PATH_i(x,y)</math> tak, aby formuła była w postaci preneksowej (wszystkie kwantyfikatory na początku). Można to jednak zrobić przesuwając je za istniejące kwantyfikatory na podstawie prostych własności logicznych.
+Następnie musimy doprowadzić część formuły bez kwantyfikatorów, czyli:
+<center><math>(((x=p\wedge t=q)\vee(t=p\wedge y=q))\Rightarrow \phi_i</math></center>
+do postaci dysjunktywnej tak, aby nie używać <math>\phi_i</math> dwukrotnie.
+Powyższa formuła jest równoważna:
+<center><math>(((x\neq p\vee t\neq q)\wedge(t\neq p\vee y\neq q))\vee
+\phi_i(p,q)</math></center>
+przy czym pierwszą część można ostatecznie zapisać przy pomocy 16 implikantów (w rzeczywistości <math>16n^{2k}</math>, gdyż przypomnijmy, że <math>x,y,p,t,q</math> odpowiadają <math>n^k</math> zmiennym binarnym).
+W ten sposób zapisanie <math>PATH_{n^k}(x,y)</math> na każdym poziomie będzie wymagało dopisania <math>16n^{2k}</math> implikantów oraz <math>3n^k</math> kwantyfikatorów, a więc ostatecznie rozmiar całej formuły będzie wielomianowy.
+Zredukowaliśmy dowolny język <math>L</math> z PSPACE do QSAT w wersji dysjunktywnej. Jest to jednak dopełnienie QSAT w wersji koniunktywnej. Stosując obustronne dopełnienie otrzymujemy redukcję dowolnego języka z coPSPACE do QSAT (w wersji koniunktywnej). Jednak PSPACE = coPSPACE, więc w rzeczywistości pokazana redukcja nam wystarcza.
+}}
+Oto przykład dwóch innych problemów, których będziemy używać w dalszej części. Ich PSPACE-zupełność jest przedmiotem ćwiczenia końcowego:
+{{definicja|2.3 [Problem IN PLACE ACCEPTANCE (akceptacja w miejscu)]|def 2.3|
+Wejście: maszyna M i słowo <math>x</math><br>
+Wyjście: czy maszyna M akceptuje słowo <math>x</math> używając <math>|x|</math> pamięci?
+}}
+{{definicja|2.4 [Problem IN PLACE DIVERGENCE (rozbieżność w miejscu)]|def 2.4|
+Wejście: maszyna M<br>
+Wyjście: czy maszyna M pętli się używając <math>|M|</math> pamięci?
+}}
+===Optymalizacja periodyczna===
+[[File:ZO-14-0a.mp4|250x250px|thumb|right|Graf periodyczny.]]
+<!-- [[ZO-14-0a-rys.jpg(Graf periodyczny)]] -->
+Wśród problemów PSPACE-zupełnych znajdują się wersje ''periodyczne'' (inaczej okresowe) znanych problemów. Jako pierwszy rozważmy problem PERIODIC GRAPH COLORING. Polega on na kolorowaniu grafu periodycznego. Poniższy przykład powinien wszystko wyjaśnić:
+W animacji [http://osilek.mimuw.edu.pl/images/1/1e/ZO-14-0a.swf Graf periodyczny] widać nieskończony graf periodyczny i jego skończony zwięzły zapis. Krawędź oznaczona etykietą <math>+1</math> oznacza, że następuje połączenie pomiędzy wierzchołkami z grup odległych o 1. W takim zapisie możemy stosować również etykiety oznaczone większymi liczbami oraz liczbami ujemnymi.
+Naszym zadaniem jest obliczenie liczby chromatycznej grafu periodycznego lub stwierdzenie czy jest mniejsza niż <math>k</math> dla wersji decyzyjnej. Dla powyższego grafu wynosi ona 2, mimo, iż graf jest nieskończony!
+Podobnie można przedstawić problem PERIODIC SAT. Tym razem formuła jest nieskończona i periodyczna, natomiast w jej zwięzłym zapisie możemy stosować klauzule postaci <math>x\vee y_{+1}\vee \neg z</math>, w których <math>+1</math> oznacza powiązanie pomiędzy zmiennymi z sąsiednich grup. Podobnie jak w normalnym SAT pytamy o istnienie wartościowania spełniającego.
+Analizowanie przedstawionych powyżej nieskończonych struktur może wydawać się zadaniem niewykonalnym, jednakże oba powyższe problemy okazują się być PSPACE-zupełne.
+{{cwiczenie|2.5|cw 2.5|
+Udowodnij, że problem PERIODIC SAT jest PSPACE-zupełny.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> Zauważ, że wartościowanie spełniające jest okresowe. Skorzystaj z problemu IN PLACE DIVERGENCE.
+</div></div>
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Pokażmy najpierw że PERIODIC SAT należy do PSPACE. Załóżmy, że wartościowanie spełniające istnieje. Jest to nieskończony ciąg wartościowań grup zmiennych <math>\ldots,X_i,X_{i+1},\ldots</math>. Rozmiary <math>X_i</math> odpowiadają zapisowi pojedynczej grupy zmiennych przedstawionym na wejściu (rozmiaru <math>n</math>).
+Łatwo zauważyć, że sąsiednie grupy mogą być wartościowane na <math>2^{2n}</math> sposobów, stąd spełniające wartościowanie nieskończone posiada okres o długości co najwyżej tego rzędu, gdyż powtórzy się w nim ta sama para wartościowań sąsiednich grup zmiennych. To pozwala nam przejść od analizy formuł nieskończonych do tych o wykładniczej ilości grup zmiennych.
+Wykorzystując maszynę niedeterministyczną zgadujemy wartościowanie wykładniczej długości dla kolejnych grup zmiennych <math>T_i</math> (w tej samej pamięci) sprawdzając na każdym etapie, czy jest spełniające w ramach grupy i odpowiedni fragment w przód i w tył na podstawie uogólnionych klauzul. Na podstawie równości NPSPACE i PSPACE otrzymujemy potrzebny algorytm.
+Teraz pokażmy zupełność problemu. Zredukujemy wspomniany PSPACE-zupełny problem IN PLACE DIVERGENCE do PERIODIC SAT.
+Bierzemy maszynę M i pytamy czy istnieje dla niej obliczenie nieskończone w miejscu. Kodujemy konfigurację maszyny w pojedynczej grupie zmiennych z problemu PERIODIC SAT. Wzorujemy się na dowodzie twierdzenia Cooka-Levina. Poprawne przejścia pomiędzy konfiguracjami kodujemy przy pomocy uogólnionych klauzul. Jeśli skonstruowana w taki sposób formuła periodyczna jest spełnialna, to w jednoznaczny sposób odpowiada to obliczeniu nieskończonemu maszyny w miejscu.
+</div></div>
+==Gry==
+Okazuje się, że klasa PSPACE to miejsce w którym zadomowiła się grupa problemów opartych na grach. Dzieje się tak dlatego, iż QSAT może w pewnej interpretacji obrazować grę dwuosobową. Kwantyfikator egzystencjalny odpowiada ruchowi gracza, który wybiera jedną z możliwości. Kwantyfikator uniwersalny odpowiada dowolnej odpowiedzi drugiego gracza. Strategia wygrywająca to taki algorytm, który pozwala wygrać pierwszemu graczowi, niezależnie od ruchów podjętych przez drugiego.
+Rozważmy grę dwuosobową powiązaną z formułą QSAT która polega na znalezieniu wartościowania spełniającego dla zmiennych przez pierwszego gracza (drugi stara się mu w tym przeszkodzić). Kolejne ruchy graczy to wybory wartości dla zmiennych <math>x_1,\ldots,x_k</math>. Na końcu następuje sprawdzenie prawdziwości formuły bez kwantyfikatorów.
+Zdefiniujmy następujący problem:
+{{definicja|3.1 [Problem FORMULA GAME]|def 3.1|
+Wejście: formuła <math>\Phi</math> jak dla QSAT <br>
+Wyjście: czy gracz I ma strategię wygrywającą dla <math>\Phi</math>?
+}}
+{{cwiczenie|3.2|cw 3.2|
+Udowodnij, że FORMULA GAME jest problemem PSPACE-zupełnym.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> Skorzystaj z redukcji QSAT do FORMULA GAME.
+</div></div>
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Po tak szeroko skomentowanej odpowiedniości pomiędzy QSAT i FORMULA GAME redukcja jest dosyć oczywista. Istnienie strategii może zostać sprawdzone w pamięci wielomianowej poprzez sprawdzenie wszystkich wartościowań stosownie do reguł gry, zupełnie tak jak działo się w dowodzie, że QSAT należy do PSPACE.
+Teraz redukcja QSAT do FORMULA GAME. Opiera się ona na własności strategii wygrywającej. Rozważmy <math>\Phi=\exists{x_1}\forall{x_2}\exists{x_3}\ldots Q{x_k}\phi</math>. Gdy posiadamy strategię wygrywającą, to istnieje taki wybór <math>x_1</math>, który sprawia, że osiągniemy sukces. Taką dokładnie wartość wybieramy dla <math>x_1</math> kwantyfikowanej egzystencjalnie. Następnie gracz II wykonuje dowolny ruch, lecz w naszej strategii jesteśmy na to przygotowani -
+tym samym <math>\phi</math> będzie prawdziwa, przy dowolnym wartościowaniu <math>x_2</math> itd. Ostatecznie formuła <math>\Phi</math> jest prawdziwa wtedy i tylko wtedy, gdy istnieje strategia wygrywająca dla FORMULA GAME. Nasza
+redukcja jest zupełnie przezroczysta - przepisuje formułę <math>\Phi</math> bezpośrednio.
+</div></div>
+[[File:ZO-14-0b.mp4|250x250px|thumb|right|Gra GEOGRAPHY.]]
+<!-- [[ZO-14-0b-rys.jpg(Gra GEOGRAPHY)]] -->
+Następnym obrazowym dla nas przykładem będzie dwuosobowa gra GEOGRAPHY, znana ze świata rzeczywistego, polegająca na kolejnym wypowiadaniu przez graczy nazw miast w ten sposób, aby każde kolejne zaczynało się na taką literą na jaką kończy się poprzednie. Nie można używać miast wielokrotnie. Przegrywa ten, kto nie może wykonać ruchu. Animacja [http://osilek.mimuw.edu.pl/images/3/30/ZO-14-0b.swf Gra GEOGRAPHY] obrazuje fragment planszy gry i możliwe
+przejścia w formie grafu.
+Aby zanalizować złożoność obliczeniową musimy dokonać pewnych technicznych zabiegów. Przede wszystkim dopuścimy dowolnie duże plansze (co już nie odpowiada rzeczywistości) oraz przekształcimy problem do postaci decyzyjnej:
+{{definicja|3.3 [Problem GEOGRAPHY]|def 3.3|
+Wejście: Graf G i wierzchołek początkowy x<br>
+Wyjście: Czy gracz I ma strategię wygrywającą?
+}}
+{{twierdzenie|3.4|tw 3.4|
+GEOGRAPHY jest problemem PSPACE-zupełnym.
+}}
+[[File:ZO-14-1.mp4|250x250px|thumb|right|Redukcja QSAT do GEOGRAPHY.]]
+<!-- [[ZO-14-1-rys.jpg(Redukcja QSAT do GEOGRAPHY)]] -->
+{{dowod|||
+Najpierw pokażmy, że GEOGRAPHY należy do PSPACE. Argument jest zupełnie podobny do tego spotkanego w QSAT. Konstruujemy algorytm rekurencyjny, który przegląda wszystkie możliwe przebiegi rozgrywki i stosownie odpowiada na pytanie. Korzystamy tutaj z odpowiedniości pomiędzy kwantyfikatorem egzystencjalnym i ruchem pierwszego gracza, oraz kwantyfikatorem uniwersalnym i ruchem drugiego gracza w analizie strategii wygrywającej. Ponieważ liczba ruchów jest ograniczona przez liczbę wierzchołków G zatem taka symulacja może odbyć się w pamięci wielomianowej.
+Następnie zredukujemy problem QSAT do GEOGRAPHY. Weźmy dowolną formułę <math>\Phi</math> i przekształćmy ją w planszę do GEOGRAPHY. Przykład postępowania dla <math>\Phi=\exists{x}\forall{y}\exists{z}( ( \neg x \vee \neg y ) \wedge (y\vee z)\wedge(y \vee \neg z))</math> przedstawiony jest w animacji [http://osilek.mimuw.edu.pl/images/0/01/ZO-14-1.swf Redukcja QSAT do GEOGRAPHY].:
+Konstrukcja jest dosyć prosta. Najpierw występuje ciąg rombów odpowiadający wartościowaniu zmiennych formuły. Zwróćmy uwagę, że plansza jest tak skonstruowana, iż wartości dla kolejnych zmiennych są wybierane przez graczy na zmianę. Tym samym gracz I ustala wartości zmiennych kwantyfikowanych egzystencjalnie, a gracz II uniwersalnie. Gdy gra dochodzi do dolnej części animacji to gracz II (bez straty ogólności zakładamy, że zmiennych jest nieparzysta ilość) wybiera wyjście odpowiadające klauzuli (w naszej interpretacji wybiera klauzulę niespełnioną). Następnie gracz I wykonuje ruch, który jest możliwy wtedy i tylko wtedy, gdy w klauzuli istnieje literał spełniony. Gracz II nie ma wtedy kolejnego ruchu.
+Pokazaliśmy tym samym równoważność strategii wygrywającej dla gracza I i prawdziwości formuły QSAT.
+}}
+Okazuje się, że jednym z ważniejszych elementów gry dwuosobowej, który powoduje, że należy ona do PSPACE, jest wielomianowe ograniczenie liczby możliwych ruchów (w tym wypadku rozmiar planszy). Podobnie stanie się gdy uogólnimy znaną dwuosobową grę planszową GO na dowolnie duże plansze. Również ona okazuje się PSPACE-zupełna.
+Przy szachach natomiast napotykamy na problem innego rodzaju. Gra ta nie poddaje się zastosowanej analizie złożoności, gdyż jej uogólnienie na dowolne plansze traci istotne wewnętrzne cechy tradycyjnej rozgrywki. W ten sposób sama gra z punktu widzenia złożoności ma rozmiar stały i wymyka się naszym metodom.
+==Złożoność wykładnicza==
+Ze względu na twierdzenia o hierarchii czasowej i pamięciowej wiemy, że rozważana w poprzednim rozdziale klasa PSPACE oczywiście nie obejmuje wszystkich języków. Naturalnym krokiem jest rozważanie klas o złożoności wykładniczej, które definiowaliśmy już wcześniej:
+* Klasa EXPSPACE <nowiki>=</nowiki> SPACE(<math>2^{n^k}</math>), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wykładniczej,
+* Klasa NEXPSPACE <nowiki>=</nowiki> NSPACE(<math>2^{n^k}</math>), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wykładniczej.
+* Klasa EXP <nowiki>=</nowiki> TIME(<math>2^{n^k}</math>), to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wykładniczym,
+* Klasa NEXP <nowiki>=</nowiki> NTIME(<math>2^{n^k}</math>), to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wykładniczym.
+Na tym wykładniczym poziomie złożoności występuje wiele podobieństwa do wielomianowych klas. Ponownie na mocy twierdzenia Savitcha wiemy, że EXPSPACE <nowiki>=</nowiki> NEXPSPACE. Wiemy także, że
+<center><math>PSPACE\subseteq EXP\subseteq NEXP \subseteq EXPSACE</math></center>
+co w połączeniu z faktem z twierdzenia hierarchii, że PSPACE zawiera się ściśle w EXPSPACE daje nam, że przynajmniej jedna z powyższych trzech nierówności jest ścisła, choć nie wiemy która.
+Podobnie:
+<center><math>P\subseteq NP \subseteq PSPACE\subseteq EXP</math></center>
+oraz wiemy, że P zawiera się ściśle w EXP, na podstawie twierdzenia o hierarchii czasowej. Stąd ponownie jedna z trzech nierówności musi być ścisła, choć nie wiemy która. Prawdopodobnie wszystkie. Najważniejsze pytanie, to czy EXP<nowiki>=</nowiki>NEXP?
+Mimo tej niewiedzy możemy udowodnić ciekawy fakt łączący hipotezy występujące na dwóch wspomnianych poziomach:
+{{cwiczenie|4.1|cw 4.1|
+Udowodnij, że jeżeli P<nowiki>=</nowiki>NP to EXP<nowiki>=</nowiki>NEXP.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> Postaraj się sztucznie "rozdmuchać" dane wejściowe.
+</div></div>
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Weźmy dowolny język L z NEXP i pokażmy, dzięki równości NP i P, że należy on do EXP.
+Załóżmy, że L jest akceptowany przez maszynę niedeterministyczną N w czasie <math>2^{n^k}</math>. Wprowadzimy teraz język <math>L'</math>, które powstaje na
+podstawie L:
+<center><math>L'=\{x\#'^{2^{|x|^k}-|x|}: x\in L\}</math></center>
+czyli innymi słowy wszystkie słowa z L, lecz unormowane do odpowiedniej długości przy użyciu quasi-blanków (jak gdyby pustych, ale odróżnialnych przez nas od pustych).
+Okazuje się, że język <math>L'</math> należy teraz do NP. Maszyna N', która
+tego dokonuje sprawdza, czy słowo ma odpowiednią długość, a następnie symuluje działanie N. Dzięki wykładniczym "rozdmuchaniu" słowa wejściowego maszyna N' ma złożoność wielomianową względem rozmiaru danych (nawet liniową).
+Na podstawie założenia P<nowiki>=</nowiki>NP wiemy, że istnieje wielomianowa maszyna deterministyczna M', która akceptuje <math>L'</math> w czasie <math>n^l</math>. Teraz dokonujemy przekształcenia w odwrotnym kierunku, otrzymując maszynę deterministyczną M, która akceptuje L w deterministycznym czasie wykładniczym <math>2^{n^l}</math>, co pokazuje, że L należy do EXP.
+Konstrukcja M to symulacja maszyny M' na słowie wejściowym. Bez straty ogólności można założyć, że maszyna traktuje taśmę wejściową jako tylko do odczytu. W tej sytuacji musimy tylko pamiętać pozycję w ciągu quasi-blanków, co nie przedstawia trudności.
+</div></div>
+W tej sytuacji pokazanie, że EXP<math>\neq</math>NEXP implikuje, że P<math>\neq</math>NP, więc jest teoretycznie trudniejszym faktem.
+Wnioski z powyższego ćwiczenia są dalej idące. Możemy mianowicie wywnioskować, że nierówność stosownych klas złożoności przenosi się w dół, natomiast równość w górę:
+{{wniosek|4.2|wn 4.2|
+Jeśli <math>g(n)\geqslant n</math> i <math>f(n)</math> są konstruowalne czasowo, to <math>\text{TIME}(f(n))=\text{NTIME}(f(n))\Rightarrow\text{TIME}(g(f(n)))=\text{NTIME}(g(f(n)))</math>
+}}
+[[File:ZO-14-2.mp4|250x250px|thumb|right|Hierarchia klas złożoności.]]
+<!-- [[ZO-14-2-rys.jpg(Hierarchia klas złożoności)]] -->
+Wszystkie wspomniane klasy złożoności wykładniczej posiadają problemy zupełne. Co warte podkreślenia, na podstawie twierdzeń o hierarchii czasowej klasa EXP nie może kolapsować do P, więc problemy EXP-zupełne nie mają rozwiązania wielomianowego, czyli nie należą do P!
+Podobnie, problemy EXPSPACE-zupełne nie należą do PSPACE, a zatem nie należą także do NP! To jednak dosyć trudna metoda wykazywania, że problem nie należy do NP.
+Na podstawie twierdzeń o hierarchii wiemy, że możemy wyróżnić coraz trudniejsze problemy i coraz większe (istotnie większe) klasy. Przykładem są klasy złożoności podwójnie wykładniczej 2EXP i 2NEXP, o których ponownie nie wiemy czy są równe.
+Jedną z ciekawych klas jest ELEMENTARY, która jest sumą klas:
+<center><math>TIME(2^{2^{\vdots^{2^{n^k}}}})</math></center>
+i nazywamy ją klasą języków elementarnych. Są jednak problemy, które i do tej klasy nie należą. Największą klasą przedstawioną w animacji [http://osilek.mimuw.edu.pl/images/6/6c/ZO-14-2.swf Hierarchia klas złożoności] obrazującym zależności pomiędzy poznanymi klasami złożoności jest R - klasa wszystkich języków rozstrzygalnych.
+===Problemy zwięzłe===
+W tej części omówimy krótko zabieg podobny do problemów periodycznych omawianych w poprzedniej części. Ponownie wprowadza on całą klasę problemów analogicznych do klasycznych takich jak SAT, czy HAMILTONIAN PATH. Problemy zwięzłe (ang. SUCCINCT) są to wersje problemów, w których wejście jest zapisane w sposób bardzo zwięzły i przez ten fakt, złożoność działania algorytmów przenosi się na wyższy poziom.
+''Zwięzła reprezentacja grafu'' <math>G</math> o <math>n=2^b</math> wierzchołkach oznaczana przez <math>G_C</math> to sieć logiczna <math>C</math> o <math>2b</math> wejściach. Gdy podamy jej na wejściu <math>i</math> i <math>j</math> zakodowane binarnie to otrzymamy jako wynik odpowiedź na pytanie czy <math>i</math> jest połączone z <math>j</math> w grafie <math>G</math>.
+Gdy przedstawimy graf wejściowy w formie zwięzłej dla HAMILTONIAN PATH (który jest problemem NP-zupełnym), to otrzymamy SUCCINCT HAMILTONIAN PATH, który będzie NEXP-zupełny poprzez zastosowanie tego samego algorytmu. Podobnie będzie w przypadku innych problemów grafowych.
+Możliwe jest również zwięzłe przedstawienie formuł i sieci logicznych. W ten sposób możemy otrzymać problemy SUCCINCT CIRCUIT VALUE i SUCCINCT CIRCUIT SAT, które są odpowiednio EXP-zupełne i NEXP-zupełne.
+===Wyrażenia regularne===
+Ciekawym polem do analizy złożoności jest standardowy język wyrażeń regularnych, w których możemy używać symboli konkatenacji, sumy zbiorów oraz <math>\star</math>:
+{{definicja|4.3 [Problem <math>EQ_{REX}</math>]|def 4.3|
+Wejście: Wyrażenia regularne R i S<br>
+Wyjście: Czy R i S są równoważne (opisują ten sam język)?
+}}
+Powyższy problem jest PSPACE-zupełny. Jeśli jednak dopuścimy dodatkowy symbol <math>\uparrow</math> - operację potęgowania, która działa następująco:
+<center><math>R^k=R\uparrow k=\overbrace{R\circ R \circ \ldots \circ R}^k</math></center>
+to otrzymujemy uogólnione wyrażenia regularne. Co ciekawe, takie rozszerzenie zmienia tylko zapis, gdyż każdą operację potęgowania można zamienić na stosowną liczbę operacji konkatenacji. Zakładamy, że <math>k</math> jest zapisane binarnie.
+{{definicja|4.4 [Problem <math>EQ_{REX\uparrow}</math>]|def 4.4|
+Wejście: Wyrażenia regularne R i S z operacją potęgowania<br>
+Wyjście: Czy R i S są równoważne?
+}}
+{{twierdzenie|4.5|tw 4.5|
+Problem <math>EQ_{REX\uparrow}</math> jest problemem EXPSPACE-zupełnym.
+}}
+{{dowod|||
+Pierwsza część dowodu to jak zwykle pokazanie przynależności problemu do klasy EXPSPACE. Eliminujemy nową operację potęgowania tak jak opisano to powyżej. Zwróćmy uwagę, że w wyniku tego procesu wyrażenia rosną wykładniczo. Następnie konstruujemy niedeterministyczne automaty skończone do rozpoznawania wyrażeń
+regularnych R i S oraz sprawdzamy ich równoważność. Ten proces może zostać wykonany w EXPSPACE w sposób następujący:
+Najpierw skonstruujemy niedeterministyczny algorytm, który sprawdza czy dwa automaty nie są równoważne, działający w czasie liniowym. Na podstawie twierdzenia Savitcha otrzymamy algorytm deterministyczny działający w czasie kwadratowym, a stąd otrzymamy algorytm deterministyczny sprawdzający czy automaty są równoważne.
+Niedeterministyczny algorytm sprawdzający nierównoważność automatów dokonuje równoległej symulacji na słowach wykładniczej długości względem ich rozmiarów (bo jeśli są różne to na takiej długości słowie). Gdy stwierdzi, że automaty dają różną odpowiedź to akceptuje.
+Do drugiej części dowodu potrzebne nam będzie pojęcie ''historii obliczeń'' maszyny Turinga. Jest to ciąg konfiguracji <math>C_1,\ldots,C_k</math> maszyny M, które przechodzi ona kolejno podczas obliczeń na słowie wejściowym <math>x</math>. Ostatnia konfiguracja jest akceptująca bądź odrzucająca. Możemy zapisać historię obliczeń w formie następującego słowa:
+<center><math>\#C_1\#\ldots\#C_k\#</math></center>
+gdzie <math>C_i</math> stanowią pełny zapis konfiguracji maszyny.
+Weźmy dowolny język L z EXPSPACE akceptowany przez maszynę M działającą w czasie <math>2^{n^k}</math>. Dla słowa <math>x</math> skonstruujemy wyrażenia regularne R i S, które są równoważne wtedy i tylko wtedy, gdy M akceptuje <math>x</math>. Idea jest bardzo prosta. R będzie generować wszystkie słowa, które zawierają symbole z dowolnej historii obliczenia maszyny M na <math>x</math>. Wyrażenie S natomiast, będzie generować wszystkie słowa, które nie są odrzucającymi historiami obliczeń. Jeśli R i S okażą się równoważne, to znaczy, że <math>x\in L</math>.
+Przenieśliśmy ciężar dowodu na konstrukcję stosownych wyrażeń regularnych, które muszą generować gigantycznej długości słowa. Wyrażenie R jest bardzo proste, gdyż ma za zadanie wygenerować wszystkie słowa nad alfabetem <math>\{\#\cup Q \cup \Gamma\}</math>, czyli <math>R= \{\#\cup Q \cup \Gamma\}^\star</math>.
+Wyrażenie Q musi natomiast pominąć słowa opisujące historie obliczeń M odrzucające <math>x</math>. Słowo takie może nie kodować odrzucającej historii obliczeń, jeśli jego początkowa lub końcowa konfiguracja jest zła, bądź w środku nie zachowuje się poprawnie. Przyjmujemy założenie, że wszystkie konfiguracje są wypełnione do prawej strony symbolami pustymi do długości <math>2^{n^k}</math>. Oznaczmy zatem przez <math>Q=Q_1\cup Q_2 \cup Q_3</math> wyrażenie regularne zawierające trzy stosowne części.
+Teraz następuje część najbardziej techniczna. Trzeba opisać wyrażeniem regularnym wszystkie możliwe nieprawidłowe podsłowa. Jest to możliwe do wykonania przy pomocy wyrażenia wielomianowej wielkości. Z pomocą przyjdzie wprowadzona operacja <math>\uparrow</math>. Nie przedstawiamy tutaj szczegółów technicznych, a do pełnej konstrukcji odsyłamy do literatury.
+}}
+Co fascynujące, gdy dodamy kolejną operację do naszych wyrażeń regularnych - negację zbioru, to okazuje się, że problem równoważności tak uogólnionych wyrażeń regularnych przestaje być elementarny!
+==Ćwiczenia dodatkowe==
+{{cwiczenie|5.1|cw 5.1|
+Udowodnij, że problemy IN PLACE ACCEPTANCE i IN PLACE DIVERGENCE są
+PSPACE-zupełne.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> Rozważ instancję problemu IN PLACE ACCEPTANCE, w którym <math>x</math> ma na końcu dopisane blanki (). Sprowadź IN PLACE ACCEPTANCE do IN PLACE DIVERGENCE.
+</div></div>
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Najpierw pokażmy, że IN PLACE ACCEPTANCE należy do PSPACE. Symulacja działania maszyny w pamięci <math>|x|</math>, czyli liniowej, jest jednak łatwa. Dodatkowo używamy licznika, który zlicza kroki maszyny (rzędu <math>c^{|x|}</math>, czyli liczby konfiguracji) aby wykryć zapętlenie.
+Weźmy teraz dowolny język L z PSPACE. Jest on akceptowany przez maszynę M w pamięci <math>n^k</math>. Oczywistym jest, że M akceptuje <math>x</math> wtedy i tylko wtedy, gdy akceptuje <math>x\#^{n^k}</math> w miejscu, bo dopisanie dowolnej liczby blanków na końcu słowa wejściowego nie ma żadnego znaczenia. Ponieważ dodatkowe blanki liczą się teraz do rozmiaru <math>x</math>, to maszyna akceptuje słowo w miejscu.
+Problem IN PLACE ACCEPTANCE zredukujemy do IN PLACE DIVERGENCE tak jak to zapowiedziano we wskazówce, pokazując tym samym PSPACE-zupełności tego ostatniego.
+Rozważmy wejście w postaci maszyny M i słowa x. Konstruujemy maszynę <math>M'</math> która rozpoczyna działanie od zapisania słowa <math>x</math> na taśmie, a następnie symuluje M zliczając jej kroki. Na końcu występuje faza przekątniowa. Gdy <math>M</math> akceptuje to <math>M'</math> przechodzi do początkowej konfiguracji i tym samym wpada w nieskończone obliczenie. Gdy <math>M</math> przekracza dozwoloną liczbę kroków (ograniczoną, gdyż maszyna działa w miejscu), to <math>M'</math> akceptuje.
+Teraz pozostaje zauważyć, że maszyna <math>M'</math> ma nieskończone obliczenie wtedy i tylko wtedy gdy <math>M</math> akceptuje słowo <math>x</math> w miejscu.
+</div></div>
+{{cwiczenie|5.2|cw 5.2|
+Pokaż że jeśli <math>g(n)\geqslant n</math> i <math>f(n)</math> są konstruowalne
+pamięciowo, to <math>\text{SPACE}(f(n))=\text{NSPACE}(f(n))\Rightarrow\text{SPACE}(g(f(n)))=\text{NSPACE}(g(f(n)))</math>.
+}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> Uogólnij dowód podobnego twierdzenia dotyczącego czasowych klas złożoności.
+</div></div>
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Zgodnie ze wskazówką weźmy dowolny język L z klasy <math>\text{NSPACE}(g(f(n)))</math>. Weźmy maszynę niedeterministyczną N
+działającą w pamięci <math>g(f(n))</math>. Wprowadzamy język:
+<center><math>L'=\{x\#'^{f^{-1}(g(f(|x|)))-|x|}: x\in L\}</math></center>
+gdzie <math>\#'</math> oznacza quasi-blanki.
+Okazuje się, że język <math>L'</math> należy teraz do <math>\text{SPACE}(f(n))</math>. Maszyna N', która tego dokonuje sprawdza, czy słowo ma odpowiednią długość, a następnie symuluje działanie N. Dzięki "rozdmuchaniu" słowa wejściowego maszyna N' ma złożoność <math>f(n)</math> .
+Ponownie na podstawie założenia <math>\text{SPACE}(f(n))=\text{NSPACE}(f(n))</math> wiemy, że istnieje maszyna deterministyczna M' która akceptuje <math>L'</math> w pamięci <math>f(n)</math>. Teraz dokonujemy przekształcenia w odwrotnym kierunku, otrzymując maszynę deterministyczną M, która akceptuje L w deterministycznej pamięci <math>g(f(n))</math>, co pokazuje, że L należy do <math>\text{SPACE}(g(f(n)))</math>.
+Uzasadnienie jest dokładnie takie samo. Maszyna M symuluje działanie maszyny M' na słowie wejściowym traktowanym jako tylko do odczytu. Jak poprzednio musimy pamiętać pozycję w ciągu quasi-blanków.
+</div></div>
+==Testy końcowe==