Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2015/16 / Komplexitätstheorie / Zwei PSPACE vollstaendige Probleme


Inhaltsbereich

Zwei PSPACE vollstaendige Probleme

Plain Text icon pspace_complete.txt — Plain Text, 3 KB (3617 bytes)

Dateiinhalt

Definition von PSPACE, QBF, PSPACE-vollstaendig von QBF, siehe [Bovet].

Problem: Universalitaet von nichtdeterministischen endlichen Automaten
(UNIV-NEA): Gegeben ist ein nichtdeterministischer endlicher Automat A
ueber einem Alphabet Sigma. Gefragt ist, ob A alle Woerter akzeptiert,
also L(A)=Sigma^*.

Satz: UNIV-NEA ist PSPACE vollstaendig.

In PSPACE: Man konstruiert den deterministischen
Potenzmengenautomaten, on demand. Genauer gesagt, sucht man im
Graphen, dessen Kanten durch die unbeschrifteten Uebergaenge des
Potenzmengenautomaten gegeben sind nach einem Pfad vom Startzustand zu
einem Nicht-Endzustand.

Fuer die PSPACE Vollstaendigkeit geben wir uns eine standardisierte
PSPACE Maschine T und eine Eingabe x vor. Alle globalen Konf haben
Groesse N=p(|x|), es gibt genau eine Startkonfiguration a_INI und eine
akzeptierende Endkonfiguration a_ACC.

Wir codieren wie ueblich Berechungnen von T auf x als Folgen der Form
a1a2a3...a_n, wobei die a_i globale Konfigurationen sind.

Sicher ist x:L(T) gdw L_x = Sigma^*, wobei L_x = U_v u V_x und 
U_x={w | w ist keine gueltige Berechnung von T auf x}
V_x={w | w endet mit a_ACC}

Wir bauen jetzt (vermittels einer FP Reduktion) aus x einen NEA A_x
mit L(A_x)=L_x:

Wir koennen U_x und V_x separat behandeln. Fuer U_x raet der Automat
nichtdeterministisch einen Fehler. Moeglichkeiten fuer solche Fehler
sind:

- Die ersten N Zeichen der Eingabe sind nicht gleich a_INI. Man
  beachte, dass der Automat poly(N) viele Zustaende haben kann und
  daher diese Pruefung festverdrahten kann.

- Die Laenge der Eingbe ist kein Vielfaches von N

- Die letzten N Symbole der Eingabe sind keine Endkonfiguration

- Die Eingabe hat die Form w1 u w2 v w3, 

  wobei |u|=|v|=3 und |w2|=N und v ist nicht Teil der entsprechenden
  Folgekonfiguration, die u enthaelt. Z.B. u,v sind beide nicht in der
  Naehe des Kopfes und unterscheiden sich trotzdem, oder u,v sind in
  der Naehe des Kopfes (um das genau zu praezisieren muesste man die
  Form der Codierung genauer fassen) und unterscheiden sich nicht
  gemaess eines Schrittes der Maschinentafel

Die Sprache V_x ist leicht zu erkennen.

Nun ist klar, dass L(A_x)=Sigma* <=> x:L(T) w.z.b.w.

PS: Setzt man voraus, dass T nur ein Band hat, Alphabet {0,1,B} und
Zustandsmenge Z disjunkt von {0,1,B}, so bietet sich folgende Codierung an:

Bandinhalt x0 x1 ... xn, Kopfposition k, Zustand z wird durch
x0 x1 .. xk z x(k+1) ... xn B B B B B B
\________________ ____________________/
                 V
	 Laenge exakt N 

codiert.


Problem: Generalized Geography (GGEO). Gegeben ein gerichteter Graph
G=(V,E) mit einem ausgezeichneten Startknoten s. Es wird folgendes
Spiel gespielt wird. Die Parteien bewegen abwechselnd eine Marke vom
Startknoten s aus entlang der Kanten. Einmal bespielte Knoten duerfen
nicht wieder besucht werden. Kann eine Partei nicht ziehen, so hat die
andere Partei gewonnen. Gefragt ist, ob die anziehende Partei eine
Gewinnstrategie hat.

Satz: GGEO ist PSPACE vollstaendig.

Beweis:

In PSPACE: Die rekursive Suche nach einem Gewinnzug kann in PSPACE (a
la Savitch) implementiert werden.

PSPACE vollstaendig. Wir geben eine Reduktion von QBF. Dabei nehmen
wir an, dass die QBF Formel in Praenex Normalform gegeben ist, dass
das Quantorenpraefix aus abwechselnden Quantoren beginnend und endend
mit Exists besteht und dass die quantorenfreie Matrix eine KNF ist.

Wir bauen aus dieser Formel ein Spiel, welches von der anziehenden
Partei gewonnen wird, gdw die Formel wahr ist. Die Details der
Konstruktion finden sich im Wikipedia Artikel
https://en.wikipedia.org/wiki/Generalized_geography.

Artikelaktionen


Funktionsleiste