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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 ]

Wejście: formuła logiczna jak dla problemu SAT poprzedzona dowolną liczbą naprzemiennych kwantyfikatorów: .
Wyjście: czy jest prawdziwa?

Przypomnijmy, że na użytek hierarchii wielomianowej definiowaliśmy problem , który mógł mieć 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 jest PSPACE-zupełny.

Dowód

{{{3}}} 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
Wyjście: czy maszyna M akceptuje słowo używając 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 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ć:

W animacji Graf periodyczny widać nieskończony graf periodyczny i jego skończony zwięzły zapis. Krawędź oznaczona etykietą 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ż 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 , w których 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

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 . 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

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.

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 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.

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(), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wykładniczej,
  • Klasa NEXPSPACE = NSPACE(), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wykładniczej.
  • Klasa EXP = TIME(), to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wykładniczym,
  • Klasa NEXP = NTIME(), 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



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:



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

W tej sytuacji pokazanie, że EXPNEXP implikuje, że PNP, 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 i są konstruowalne czasowo, to

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:

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 o wierzchołkach oznaczana przez to sieć logiczna o wejściach. Gdy podamy jej na wejściu i zakodowane binarnie to otrzymamy jako wynik odpowiedź na pytanie czy jest połączone z w grafie .

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 ]

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:



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 jest zapisane binarnie.

Definicja 4.4 [Problem ]

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 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 maszyny M, które przechodzi ona kolejno podczas obliczeń na słowie wejściowym . Ostatnia konfiguracja jest akceptująca bądź odrzucająca. Możemy zapisać historię obliczeń w formie następującego słowa:



gdzie stanowią pełny zapis konfiguracji maszyny.

Weźmy dowolny język L z EXPSPACE akceptowany przez maszynę M działającą w czasie . Dla słowa skonstruujemy wyrażenia regularne R i S, które są równoważne wtedy i tylko wtedy, gdy M akceptuje . Idea jest bardzo prosta. R będzie generować wszystkie słowa, które zawierają symbole z dowolnej historii obliczenia maszyny M na . 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 .

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 , czyli .

Wyrażenie Q musi natomiast pominąć słowa opisujące historie obliczeń M odrzucające . 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 . Oznaczmy zatem przez 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.

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
Rozwiązanie

Ćwiczenie 5.2

Pokaż że jeśli i są konstruowalne pamięciowo, to .

Wskazówka
Rozwiązanie

Testy końcowe