Mariusz Redwanz

GEO ϵ PSPACE-complete

Definicja PSPACE

Klasa problemów decyzyjnych, które mogą być rozwiązane przez maszynę Turinga przy użyciu wielomianowej pamięci.

Definicja PSPACE-complete

Problem decyzyjny jest PSPACE-zupełny, jeżeli znajduje się w klasie PSPACE i każdy problem w PSPACE może być zredukowany do niego w czasie wielomianowym. Problemy, które są PSPACE-zupełne można traktować jako najtrudniejsze problemy w PSPACE, ponieważ rozwiązanie jednego takiego problemu może być łatwo użyte do rozwiązania innego problemu w PSPACE.

Gra geografia (GEO)

Geografia jest popularną grą. Bierze w niej udział dwóch graczy, nazwanych I i II. Gracz I rozpoczyna grę, podając nazwę pierwszego miasta, powiedzmy Gdańsk. Gracz II musi wówczas znaleźć miasto, którego nazwa rozpoczyna się od ostatniej litery poprzednio wymienionego miasta, na przykład Kraków. Gracz I musi odpowiedzieć kolejną nazwą, przy czym wszystkie nazwy użyte wcześniej przez któregokolwiek z graczy, nie mogą być ponownie wykorzystana w trakcie gry. Ten z graczy, który nie może wykonać ruchu przegrywa.

Możemy przekształcić tę grę następująco: mamy graf skierowany G = (V,E), którego wierzchołkami są wszystkie miasta świata; krawędź z miasta i do miasta j istnieje wtedy i tylko wtedy, gdy ostatnia litera nazwy i jest taka sama, jak pierwsza litera nazwy j. Gracz I wybiera wierzchołek 1, potem gracz II wybiera wierzchołek, do którego prowadzi wierzchołek z 1, itd. W ten sposób gracze wyznaczają na zmianę ścieżkę w grafie G. Przegrywa ten gracz, który nie może poprowadzić dalej ścieżki, gdyż wszystkie wierzchołki, do których istnieje krawędź z wierzchołka, w którym się on aktualnie znajduje, zostały już wykorzystane.

Skupmy się na następującym problemie obliczeniowym:

GEOGRAPHY: Czy dla danego grafu G i wierzchołka początkowego 1 gracz I ma strategię wygrywającą?

Twierdzenie

Problem GEOGRAPHY jest PSPACE-zupełny.

Dowód

Gra GEOGRAPHY ma dwie następujące, ważne cechy:

1. Długość dowolnego poprawnego ciągu ruchów jest wielomianowo ograniczona przez rozmiar danych; w szczególności, gra musi zakończyć się po najwyżej |V| ruchach.

2. Istnieje algorytm, który na podstawie „stanu planszy” (tzn. grafu, ścieżki z wierzchołka 1 i informacji, kto ma teraz wykonać ruch) konstruuje wszystkie możliwe kolejne ruchy i stany planszy lub, gdy żaden ruch nie jest możliwy, decyduje kto wygrał: I czy II gracz.

Dowolną taką grę możemy rozwiązać w PSPACE. Dla zadanego wejścia konstruujemy w wielomianowej pamięci „drzewo gry” – drzewo stanów planszy rozpoczynające się od sytuacji początkowej. Liście drzewa otrzymują wartości true lub false w zależności od tego, czy odpowiadają wygranej czy przegranej gracza I. Dowolną sytuację na planszy nie będącą liściem traktujemy jak bramkę OR, gdy jest kolej na ruch gracza I, i jak bramkę AND, gdy ruch należy do II. Możemy uniknąć bramek o więcej niż dwóch poprzednikach, zastępując każdą taką bramkę przez drzewo binarne o odpowiedniej liczbie bramek tego samego rodzaju. Wszystko to możemy wykonać w pamięci wielomianowej. Potem możemy obliczyć w pamięci wielomianowej całe drzewo, by uzyskać odpowiedź dla zadanych danych wejściowych.

Zredukujemy teraz problem QSAT do GEOGRAPHY. Rozważmy następujący przykład QSAT:

$$\varphi = \exists x\forall y\exists z\left\lbrack \left( \neg x\ V\ \neg y \right)\hat{}\left( y\ V\ z \right)\hat{}\left( y\ V\ \neg z \right) \right\rbrack$$

Konstruujemy graf: każdą zmienną zastępujemy „elementem wyboru” przypominającym diament i wszystkie takie elementy łączymy w łańcuch; wierzchołkiem początkowym jest górny diament odpowiadający pierwszej zmiennej; dowolna ścieżka rozpoczynająca się w wierzchołku początkowym grafu biegnie jedną z dwóch stron każdego diamentu; taką ścieżkę możemy uważać za wartościowanie zmiennych, gdzie przejście w dół jedną stroną diamentu reprezentuje wartość true dla tej zmiennej, a druga strona reprezentuje wartość false. Gracz I wybiera wartości dla wszystkich zmiennych egzystencjalnych (∃), a gracz II dla wszystkich zmiennych uniwersalnych (∀). Węzeł k jest dodawany w zależności od równej ilości zmiennych, tak aby gracz II wybierał węzeł za węzłem b. Na koniec gracz II wybiera wierzchołek odpowiadający klauzuli, chcąc udowodnić, że klauzula nie jest spełniona przez wybrane wartościowanie (są to dolne wierzchołki grafu). Jedyne wierzchołki dostępne dla gracza I w kolejnym ruchu, to środkowe wierzchołki diamentów odpowiadających literałom w tej klauzuli. Jeżeli w klauzuli nie ma prawdziwego literału, to gracz I nie może wykonać ruchu, a więc przegrywa. Jeżeli w klauzuli istnieje literał, który powoduje jej prawdziwość (tzn. literał, przez który nie biegnie ścieżka), to gracz I przechodzi do tego literału, a gracz II przegrywa w następnym kroku.

Przypuśćmy, że w powstałym grafie możliwa jest wygrana gracza I. To oznacza, że niezależnie od tego jak gra II gracz, gracz I może wybrać ścieżkę, która doprowadzi gracza II do wykorzystanego już miasta. Ale to oznacza, że gracz I może tak wybrać przejście przez pierwszy diament, że dla każdego przejścia gracza II przez drugi diament istnieje wybór dla gracza I itd. dla pozostałych diamentów, w których niezależnie od wyboru wierzchołka dokonanego przez gracza II, gracz I zawsze może wybrać niewykorzystany literał.

Na podstawie powyższej strategii można łatwo opisać strategię prowadzącą do wygranej przez gracza I w zadanym przykładzie QSAT: gracz I ma wybór dla x₁, taki że dla obu możliwości wyboru gracza II dla x₂ itd., dla każdej klauzuli istnieje prawdziwy literał, a więc zadany przykład QSAT ma wartość true.