Złożoność obliczeniowa/Wykład 14: Pamięć wielomianowa i złożoność wykładnicza

From Studia Informatyczne

Spis treści

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 \textnormal{QSAT}]

Wejście: formuła logiczna \phi jak dla problemu SAT poprzedzona dowolną liczbą naprzemiennych kwantyfikatorów: \Phi=\exists{x_1}\forall{x_2}\exists{x_3}\ldots Q{x_k}\phi.
Wyjście: czy \Phi jest prawdziwa?

Przypomnijmy, że na użytek hierarchii wielomianowej definiowaliśmy problem \textnormal{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 \textnormal{QSAT} jest PSPACE-zupełny.

Dowód

{{{3}}} image:End_of_proof.gif

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\vee y_{+1}\vee \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

Zauważ, że wartościowanie spełniające jest okresowe. Skorzystaj z problemu IN PLACE DIVERGENCE.

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 \ldots,X_i,X_{i+1},\ldots. 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^{2n} 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,\ldots,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 \Phi jak dla QSAT
Wyjście: czy gracz I ma strategię wygrywającą dla \Phi?

Ćwiczenie 3.2

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

Wskazówka

Skorzystaj z redukcji QSAT do FORMULA GAME.

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 \Phi=\exists{x_1}\forall{x_2}\exists{x_3}\ldots Q{x_k}\phi. 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 \phi będzie prawdziwa, przy dowolnym wartościowaniu x_2 itd. Ostatecznie formuła \Phi jest prawdziwa wtedy i tylko wtedy, gdy istnieje strategia wygrywająca dla FORMULA GAME. Nasza redukcja jest zupełnie przezroczysta - przepisuje formułę \Phi 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łę \Phi i przekształćmy ją w planszę do GEOGRAPHY. Przykład postępowania dla \Phi=\exists{x}\forall{y}\exists{z}( ( \neg x \vee \neg y ) \wedge (y\vee z)\wedge(y \vee \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.

image:End_of_proof.gif

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


PSPACE\subseteq EXP\subseteq NEXP \subseteq EXPSACE


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 NP \subseteq PSPACE\subseteq EXP


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

Postaraj się sztucznie "rozdmuchać" dane wejściowe.

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\neqNEXP implikuje, że P\neqNP, 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)\geqslant n i f(n) są konstruowalne czasowo, to \textnormal{TIME}(f(n))=\textnormal{NTIME}(f(n))\Rightarrow\textnormal{TIME}(g(f(n)))=\textnormal{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:

TIME(2^{2^{\vdots^{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 2b 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 \star:

Definicja 4.3 [Problem EQ_{REX}]

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 \uparrow - operację potęgowania, która działa następująco:


R^k=R\uparrow k=\overbrace{R\circ R \circ \ldots \circ R}^k,


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 EQ_{REX\uparrow}]

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 EQ_{REX\uparrow} 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,\ldots,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\#\ldots\#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 \Gamma\}, czyli R= \{\#\cup Q \cup \Gamma\}^\star.

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 \uparrow. Nie przedstawiamy tutaj szczegółów technicznych, a do pełnej konstrukcji odsyłamy do literatury.

image:End_of_proof.gif

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)\geqslant n i f(n) są konstruowalne pamięciowo, to \textnormal{SPACE}(f(n))=\textnormal{NSPACE}(f(n))\Rightarrow\textnormal{SPACE}(g(f(n)))=\textnormal{NSPACE}(g(f(n))).

Wskazówka

Uogólnij dowód podobnego twierdzenia dotyczącego czasowych klas złożoności.

Rozwiązanie

Zgodnie ze wskazówką weźmy dowolny język L z klasy \textnormal{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 \textnormal{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 \textnormal{SPACE}(f(n))=\textnormal{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 \textnormal{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.

Testy końcowe