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

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{QSAT}} :
Wejście: formuła logiczna $\varphi$ jak dla problemu SAT poprzedzona dowolną liczbą naprzemiennych kwantyfikatorów: $\mathrm{\Phi }=\mathrm{\exists }{x}_1\mathrm{\forall }{x}_2\mathrm{\exists }{x}_3\dots Q{x}_k\varphi$.
Wyjście: czy $\mathrm{\Phi }$ jest prawdziwa?

Przypomnijmy, że na użytek hierarchii wielomianowej definiowaliśmy problem Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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

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

ZO-14-0a-rys.jpg(Graf periodyczny)

Na powyższym rysunku 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 \mathrm{\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 $\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^{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.