ls1- · Tiling-Puzzle (1/2) •Wir betrachten ein Kachel-Puzzle (englisch für „Kachel“: Tile)...

KomplexitätstheorieTeil A: Klassische Klassen

2: Puzzle und Speicherplatz

Version von: 9. April 2015 (17:59)

Sommersemester 2015 - Thomas Schwentick

Kacheln - Tiles

Kompl.-Theorie / Schwentick / SoSe 15 A: 2. Puzzle und Speicherplatz . ✁✄ Folie 1

Kachel-Puzzle


Kachel-Puzzle mit einer Spielerin


Inhalt

✄ 2.1 Tiling-Puzzle

2.2 Speicherplatzbasierte Komplexitätsklassen

2.3 Vollständige Probleme für PSPACE


Tiling-Puzzle (1/2)

• Wir betrachten ein Kachel-Puzzle(englisch für „Kachel“: Tile)

• Gespielt wird mit Kacheln der Art ,wobei jeweils nur vorgegebene Sortenvon Kacheln mit bestimmten Färbun-gen verfügbar sind

• Von jeder Sorte sind beliebig viele Ka-cheln verfügbar

• Die Kacheln müssen in einem Recht-eck angeordnet werden

• Die Kacheln dürfen nicht gedreht wer-den

• Oben und unten muss das Rechteckeinfarbig blau abschließen

• Benachbarte Kacheln müssen an derangrenzenden Seite die selbe Farbehaben


Tiling-Puzzle (1/2)








Beispiel

• c = 4, r = 5

• Puzzlesteine:

, , , , , , , , ,

, ,


Tiling-Puzzle (1/2)








Beispiel

• c = 4, r = 5

• Puzzlesteine:

, , , , , , , , ,

, ,

• Mögliche Lösung:


Tiling-Puzzle (2/2)Definition

• Sei T eine Menge von Kacheln

• o,w,n,s seien vier Funktionen T → Fin eine Menge F von Farben

• Eine c× r-Lösung für ei-ne Menge T ist eine FunktionK : {1, . . . ,c} × {1, . . . ,r} → T ,so dass gelten:

◮ Für alle j ∈ {1, . . . ,c} gilt:� s(K(j,1)) = blau ☞ untere Reihe

� n(K(j,r)) = blau ☞ obere Reihe

◮ Für alle i ∈ {1, . . . ,c− 1} und allej ∈ {1, . . . ,r} gilt:e(K(i,j)) = w(K(i+ 1,j))

☞ horizontal ok

◮ Für alle i ∈ {1, . . . ,c} und allej ∈ {1, . . . ,r − 1} gilt:

n(K(i,j)) = s(K(i,j + 1))☞ vertikal ok

!Kompl.-Theorie / Schwentick / SoSe 15 A: 2. Puzzle und Speicherplatz . ✁✄ Folie 6








☞ horizontal ok



Beispiel

• n( ) = grün

• s( ) = rot

• e( ) = blau

• w( ) = weiß









☞ horizontal ok



Beispiel

• n( ) = grün

• s( ) = rot

• e( ) = blau

• w( ) = weiß

Definition: TILING

Gegeben: Kachelmenge T und Zahlen c, r(unär kodiert!)

Frage: Gibt es eine c×r-Lösung für T ?









☞ horizontal ok



Beispiel

• n( ) = grün

• s( ) = rot

• e( ) = blau

• w( ) = weiß

Definition: TILING



Definition: CORRIDORTILING

Gegeben: Kachelmenge T und Zahl c(unär kodiert!)

Frage: Gibt es eine c×r-Lösung für T(für irgendein r)?









☞ horizontal ok



Beispiel

• n( ) = grün

• s( ) = rot

• e( ) = blau

• w( ) = weiß

Definition: TILING



Definition: CORRIDORTILING

Gegeben: Kachelmenge T und Zahl c(unär kodiert!)

Frage: Gibt es eine c×r-Lösung für T(für irgendein r)?

• Was ist die Komplexität von TILING undCORRIDORTILING?


Korridor-Puzzle


Komplexität von Tiling-Puzzles (1/2)Satz 2.1

• TILING ist vollständig für NP




Beweisskizze

• Klar: TILING ∈ NP




Beweisskizze


• Für den Beweis der NP-Vollständigkeit zei-gen wir, dass jedes L ∈ NP auf TILINGreduzierbar ist




Beweisskizze


• Für den Beweis der NP-Vollständigkeit zei-gen wir, dass jedes L ∈ NP auf TILINGreduzierbar ist• SeiM eine TM, die◮ L nichtdeterministisch entscheidet,◮ für Eingaben der Länge n Zusatzeinga-

ben der Länge nℓ verwendet, und

◮ Laufzeit nk hat (OBdA: k ≥ ℓ)




Beweisskizze




◮ Laufzeit nk hat (OBdA: k ≥ ℓ)• Sei x ein String und n

def= |x|




Beweisskizze





def= |x|

• Für i,j ≤ nk definieren wir rijdef=

◮ (σ,q), wenn nach i Schritten vonM(x) der Kopf in Zustand q an Positi-on j steht und sich dort ein σ befindet

◮ σ, wenn nach i Schritten vonM(x)an Position j ein σ steht und der Kopfsich woanders befindet




Beweisskizze





def= |x|




Beweisskizze (Forts.)

• Die Farben der Tilingsteine sind Paare(r,r′) von Einträgen aus Γ ∪ (Γ × Q)mit der Intention:

◮ Bei „Ost-“ und „Nordfarben“ ist r der„Wert“ des aktuellen Feldes und r′ derWert des anliegenden Nachbarfeldes

◮ Bei „Süd-“ und „West-“ ist es umgekehrt




Beweisskizze





def= |x|








• Die zulässigen Steine ergeben sich dannaus der Überführungsfunktion vonM ⊞




Beweisskizze





def= |x|









• Für die unterste und oberste Zeile werdennoch spezielle Steine eingeführt

(abhängig von der Eingabe x)

• Dann lässt sich zeigen:M akzeptiert x⇐⇒ es gibt eine

nk × nk-Lösung des Puzzles




Beweisskizze





def= |x|









• Für die unterste und oberste Zeile werdennoch spezielle Steine eingeführt

(abhängig von der Eingabe x)

• Dann lässt sich zeigen:M akzeptiert x⇐⇒ es gibt eine

nk × nk-Lösung des Puzzles

✎ Um die Komplexität von CORRIDORTILING zucharakterisieren, müssen wir etwas weiter aus-holen: Ressource Speicherplatz


Inhalt

2.1 Tiling-Puzzle

✄ 2.2 Speicherplatzbasierte Komplexitätsklas-sen

2.3 Vollständige Probleme für PSPACE


Speicherplatzaufwand (1/2)

• Wie soll Speicherplatz gemessen werden?




◮ wir zählen die benutzten „Felder“ der Strings einerTM




◮ wir zählen die benutzten „Felder“ der Strings einerTM

• Komplikation:

◮ wir werden uns später auch für sehr kleinen Spei-cherplatz interessieren (O(logn))

◮ Aber: allein die Eingabe nimmt n Felder in An-spruch

➞ Deshalb zählen wir den Eingabestring nicht mitund erlauben der TM keine Änderungen aufdem Eingabestring


Speicherplatzaufwand (2/2)Definition

• Eine k-string TM mit read-only Ein-

gabestring (RO-TM) ist eine k-string TM

M = (Q,Σ,Γ,δ,s) mit:

◮ Ist δ(q,σ1, . . . ,σk) =(q′,σ′

1, . . . ,σ′k,d1, . . . ,dk), so ist

(a) σ1 = σ′1, und

(b) falls σ1 = ⊔, so d1 =←.






◮ Ist δ(q,σ1, . . . ,σk) =(q′,σ′

1, . . . ,σ′k,d1, . . . ,dk), so ist

(a) σ1 = σ′1, und

(b) falls σ1 = ⊔, so d1 =←.

• Ist (q,(w1,z1), . . . ,(wk,zk)) die Hal-tekonfiguration vonM bei Eingabe x soist der Speicherplatzaufwand vonM beiEingabe x:

sM(x)def=

∑ki=2 |wi|






◮ Ist δ(q,σ1, . . . ,σk) =(q′,σ′

1, . . . ,σ′k,d1, . . . ,dk), so ist

(a) σ1 = σ′1, und

(b) falls σ1 = ⊔, so d1 =←.


sM(x)def=

∑ki=2 |wi|

• S : N 7→ R heißt Platzschranke fürM ,falls für ein n0 und alle x mit |x| > n0gilt:

sM(x) ≤ S(|x|)



•• Eine k-string TM mit read-only Ein-



◮ Ist δ(q,σ1, . . . ,σk) =(q′,σ′

1, . . . ,σ′k,d1, . . . ,dk), so ist

(a) σ1 = σ′1, und

(b) falls σ1 = ⊔, so d1 =←.


sM(x)def=

∑ki=2 |wi|


sM(x) ≤ S(|x|)

Definition

•• SPACEk(S): Sprachen L, die von RO-k-

TM mit PlatzschrankeO(S) entschiedenwerden

• SPACE(S):⋃

k≥2

SPACEk(S)

• PSPACE:⋃

ℓ≥1

SPACE(nℓ)






◮ Ist δ(q,σ1, . . . ,σk) =(q′,σ′

1, . . . ,σ′k,d1, . . . ,dk), so ist

(a) σ1 = σ′1, und

(b) falls σ1 = ⊔, so d1 =←.


sM(x)def=

∑ki=2 |wi|


sM(x) ≤ S(|x|)

Definition

•• SPACEk(S): Sprachen L, die von RO-k-

TM mit PlatzschrankeO(S) entschiedenwerden

• SPACE(S):⋃

k≥2

SPACEk(S)

• PSPACE:⋃

ℓ≥1

SPACE(nℓ)

✎ Für die Definition von PSPACE ist die Be-schränkung auf RO-TMs eigentlich nicht nö-tig

◮ Wir können im Folgenden also anneh-men, dass „PSPACE-TMs“ nur mit einemString arbeiten...


2-string-RO-TM: BeispielBeispiel

• 2-String-Turing-Maschine zum Test, ob die Eingabe von der FormwwR ist:

a: Kopiere String vom ersten auf den zweiten String (bis blank)

b/c: Bewege Kopf 2 zurück an Anfang, teste dabei, ob die Anzahlder Zeichen gerade oder ungerade ist

d: Bewege Kopf 1 nach links, Kopf 2 nach rechts, vergleiche je-weils die gelesenen Zeichen

✄

✄

0 1 1 1 1 0ba







✄

✄

0 1 1 1 1 0ba

⊔







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

b







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bc







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcb







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbc







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcb







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbc







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcb







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcbd







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcbdd







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcbddd







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcbdddd







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcbddddd







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcbdddddd







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcbddddddd







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcbddddddd+







✄

✄

0 1 1 1 1 0ba

⊔

a

0 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a

1 ⊔

a ⊔

0 ⊔

bcbcbcbddddddd+

• Die letzte Konfiguration der Beispielberechnung ist(„ja“,(ǫ,✄ ,011110⊔),(✄011110, ⊔ ,ǫ))

• Der benötigte Speicherplatz ist also|✄011110|+ |⊔|+ |ǫ| = 8


Inhalt

2.1 Tiling-Puzzle

2.2 Speicherplatzbasierte Komplexitätsklassen

✄ 2.3 Vollständige Probleme für PSPACE


CorridorTiling ist vollständig für PSPACESatz 2.2

• CORRIDORTILING ist vollständig für PSPACE




Beweisskizze

• Der Beweis der unteren Schranke ergibt sich durch recht einfacheModifikationen des Beweises von Satz 2.1:




Beweisskizze


◮ Die TM hat keine Zusatzeingabe✎ das vereinfacht die Sache sogar




Beweisskizze



◮ Es ist keine Laufzeitschranke vorgegeben➞ dies entspricht der Tatsache, dass für CORRIDORTILING kei-

ne Zeilenzahl vorgegeben ist




Beweisskizze





◮ Durch die Speicherplatzschranke ist jedoch eine Schranke fürdie Spaltenzahl vorgegeben




Beweisskizze






• Für die obere Schranke:◮ es ist leicht zu sehen, dass CORRIDORTILING nichtdetermi-

nistisch durch eine TM mit polynomieller Platzschranke ent-schieden werden kann� Sie „rät“ und überprüft die Lösung Zeile für Zeile

- und muss dafür immer nur zwei Zeilen speichern




Beweisskizze






• Für die obere Schranke:◮ es ist leicht zu sehen, dass CORRIDORTILING nichtdetermi-

nistisch durch eine TM mit polynomieller Platzschranke ent-schieden werden kann� Sie „rät“ und überprüft die Lösung Zeile für Zeile

- und muss dafür immer nur zwei Zeilen speichern◮ In Kapitel 6 werden wir sehen, dass das genügt um

CORRIDORTILING ∈ PSPACE zu folgern


NFA-CONTAINMENT ist PSPACE-vollständig (1/2)

• Um zu testen, ob die (endlichen)Läufe eines durch einen Automa-tenA1 spezifizierten Systemseine durch einen AutomatenA2spezifizierten Eigenschaft ha-ben, kann getestet werden, obL(A1) ⊆ L(A2) gilt




Definition: NFA-CONTAINMENT

Gegeben: NFAsA1,A2

Frage: Ist L(A1) ⊆ L(A2)?





Gegeben: NFAsA1,A2


• L(A1) ⊆ L(A2) gilt genaudann, wenn

L(A1) ∩ L(A2) = ∅





Gegeben: NFAsA1,A2



L(A1) ∩ L(A2) = ∅

• WennA1 undA2 DFAs sind, istdieser Test über die Produktkon-struktion in polynomieller Zeit mög-lich





Gegeben: NFAsA1,A2



L(A1) ∩ L(A2) = ∅


• Was ist, wennA2 ein NFA ist?





Gegeben: NFAsA1,A2



L(A1) ∩ L(A2) = ∅



Satz 2.3 [Hunt et al., 76]

• NFA-CONTAINMENT ist PSPACE-vollständig





Gegeben: NFAsA1,A2



L(A1) ∩ L(A2) = ∅





Beweisskizze

• NFA-CONTAINMENT ∈ PSPACE:

◮ Wir skizzieren einen Algorithmus, der das Kom-plement von NFA-CONTAINMENT nichtdetermi-stisch mit polynomiellem Speicherplatz entschei-det

✎ Wie gesagt: in Kapitel 6 werden wir sehen,dass das genügt...





Gegeben: NFAsA1,A2



L(A1) ∩ L(A2) = ∅





Beweisskizze




◮ Der Algorithmus ist ein Nicht-Leerheitstest fürden ProduktautomatenA1 × B2, wobei B2„on the fly“ aus dem Potenzmengenautomaten fürA2 durch Vertauschen der akzeptierenden undablehnenden Zustände resultiert





Gegeben: NFAsA1,A2



L(A1) ∩ L(A2) = ∅





Beweisskizze





◮ Der Algorithmus „rät“ ein Wortw Zeichen fürZeichen und speichert jeweils den Zustand q1des AutomatenA1 und die ZustandsmengeS ⊆ Q2 des Potenzmengenautomaten zuA2





Gegeben: NFAsA1,A2



L(A1) ∩ L(A2) = ∅





Beweisskizze





◮ Der Algorithmus „rät“ ein Wortw Zeichen fürZeichen und speichert jeweils den Zustand q1des AutomatenA1 und die ZustandsmengeS ⊆ Q2 des Potenzmengenautomaten zuA2

◮ Dafür reicht polynomieller Speicherplatz


NFA-CONTAINMENT ist PSPACE-vollständig (2/2)Beweisskizze (Forts.)

• Wir bezeichnen mit CORRIDORTILING dasKomplement von CORRIDORTILING

• Da PSPACE unter Komplementbildungabgeschlossen ist, ist CORRIDORTILING

ebenfalls PSPACE-vollständig ⊞






• Wir zeigen nun:

CORRIDORTILING ≤p NFA-CONTAINMENT

➨ NFA-CONTAINMENT ist PSPACE-schwierig

➨ NFA-CONTAINMENT ist PSPACE-vollständig






• Wir zeigen nun:




• Sei T eine Menge von Kacheln undc ∈ N






• Wir zeigen nun:





• Wir konstruieren NFAsA1,A2 mit:(T,1c) ∈ CORRIDORTILING ⇐⇒

L(A1) ⊆ L(A2) (∗)






• Wir zeigen nun:






L(A1) ⊆ L(A2) (∗)


• A1 akzeptiert alle Strings über T derForm u1u2 · · ·ur , wobei

◮ für alle i: |ui| = c,

◮ in u1 sind alle Kacheln unten blau, und

◮ in ur sind alle Kacheln oben blau






• Wir zeigen nun:






L(A1) ⊆ L(A2) (∗)






• A2 akzeptiert alle Strings, die zwei nichtzusammenpassende Kacheln enthalten

◮ in horizontaler Richtung oder

◮ in vertikaler Richtung






• Wir zeigen nun:






L(A1) ⊆ L(A2) (∗)









• L(A1) ⊆ L(A2) gilt also genau dann,wenn jedes hinsichtlich der Länge und derFärbung der ersten und der letzten Zeilekorrekte Tiling einen Fehler enthält






• Wir zeigen nun:






L(A1) ⊆ L(A2) (∗)










• Dies ist genau dann der Fall, wenn es kei-ne c× r-Lösung gibt






• Wir zeigen nun:






L(A1) ⊆ L(A2) (∗)










• Dies ist genau dann der Fall, wenn es kei-ne c× r-Lösung gibt

• Details: siehe Übungsaufgabe


QBF: Quantifizierte Boolesche Formeln

• Die Frage, ob die SAT-Formelϕ = (x1 ∨ x2) ∧ (¬x1 ∨ ¬x2)

erfüllbar ist, ist äquivalent zu der Frage, ob∃x1∃x2ϕ wahr ist

◮ wobei die Quantoren über {0,1} „laufen“






• Wir erlauben nun auch Allquantoren in aussagen-logischen Formeln, z.B.:∀x1∃x2((x1 ∨ x2) ∧ (¬x1 ∨ ¬x2))

• Die Menge der wahren quantifizierten aussagen-logischen Formeln (in Pränex-Normalform), de-ren quantorenfreie Matrix in KNF ist, bezeichnenwir mit QBF

◮ Auf eine formale Definition der Semantik vonQBF-Formeln verzichten wir









Satz 2.4

• QBF ∈ PSPACE

Beweisidee

• Mit einer QBF-Formel mitm Quanto-ren lässt sich in natürlicher Weise einbinärer Baum T der Tiefem verbin-den ⊞

• Der Wert von ϕ kann entlang T sy-stematisch ausgewertet werden

• T hat Tiefem

➨ SpeicherplatzO(m logm) reichtaus









Satz 2.4

• QBF ∈ PSPACE

Beweisidee

• Mit einer QBF-Formel mitm Quanto-ren lässt sich in natürlicher Weise einbinärer Baum T der Tiefem verbin-den ⊞

• Der Wert von ϕ kann entlang T sy-stematisch ausgewertet werden

• T hat Tiefem

➨ SpeicherplatzO(m logm) reichtaus

• Wir wollen jetzt zeigen, dass QBF auchPSPACE-schwierig ist

• Dazu verwenden wir das Konzept des„Konfigurationsgraphen“


Der Konfigurationsgraph einer Berechnung

• Für eine String-Zeiger-Beschreibungs = (w,z) bezeichne s den Stringw

Definition

• SeiM eine k-String-RO-TM mitPlatzschranke S• Sei x eine Eingabe fürM der Län-

ge n

• K(M,S,x): Menge aller Konfigu-

rationen (q,s1, . . . ,sk) mit

◮ s1 = ✄x oder s1 = ✄x⊔

◮ und

k∑

i=2

|si| ≤ S(|x|)




Definition


ge n



◮ s1 = ✄x oder s1 = ✄x⊔

◮ und

k∑

i=2

|si| ≤ S(|x|)

• K(M,S,x) enthält also zumindestalle Konfigurationen, die in einer Be-rechnung mit Eingabe x und Platz-schranke S „im Prinzip“ vorkommenkönnen




Definition


ge n



◮ s1 = ✄x oder s1 = ✄x⊔

◮ und

k∑

i=2

|si| ≤ S(|x|)


• FürK = (q,s1, . . . ,sk), si = (wi,zi) sei

◮ cs(K)def= (q,z1,s2, . . . ,sk),

◮ also die Kodierung vonK , in der statt s1 nurdie Position des Zeigers auf String 1 als Binär-string repräsentiert wird




Definition


ge n



◮ s1 = ✄x oder s1 = ✄x⊔

◮ und

k∑

i=2

|si| ≤ S(|x|)



◮ cs(K)def= (q,z1,s2, . . . ,sk),


• Klar: FürK ∈ K(M,S,x) gilt:

◮ |cs(K)| ≤ log(|Q|) + log(|x|)+S(|x|) + 5k + 2




Definition


ge n



◮ s1 = ✄x oder s1 = ✄x⊔

◮ und

k∑

i=2

|si| ≤ S(|x|)



◮ cs(K)def= (q,z1,s2, . . . ,sk),



◮ |cs(K)| ≤ log(|Q|) + log(|x|)+S(|x|) + 5k + 2

• Cs(M,S,x)def=

{cs(K) | K ∈ K(M,S,x)}




Definition


ge n



◮ s1 = ✄x oder s1 = ✄x⊔

◮ und

k∑

i=2

|si| ≤ S(|x|)



◮ cs(K)def= (q,z1,s2, . . . ,sk),



◮ |cs(K)| ≤ log(|Q|) + log(|x|)+S(|x|) + 5k + 2

• Cs(M,S,x)def=

{cs(K) | K ∈ K(M,S,x)}

• KonfigurationsgraphGs(M,S,x):

◮ Knotenmenge:Cs(M,S,x)

◮ Kante (cs(K),cs(K′)), fallsK ⊢M K′




Definition


ge n



◮ s1 = ✄x oder s1 = ✄x⊔

◮ und

k∑

i=2

|si| ≤ S(|x|)



◮ cs(K)def= (q,z1,s2, . . . ,sk),



◮ |cs(K)| ≤ log(|Q|) + log(|x|)+S(|x|) + 5k + 2

• Cs(M,S,x)def=

{cs(K) | K ∈ K(M,S,x)}

• KonfigurationsgraphGs(M,S,x):

◮ Knotenmenge:Cs(M,S,x)

◮ Kante (cs(K),cs(K′)), fallsK ⊢M K′

Lemma 2.5

• Ist S(n) ≥ logn, so hatGs(M,S,x)

höchstens 2O(S(|x|)) Knoten


Notation

• Endliche Folgen x1, . . . ,xn aus-agenlogischer Variablen schreibenwir im Folgenden in Vektorschreib-weise: ~x = x1, . . . ,xn

• Sind ~y = y1, . . . ,yn und~z = z1, . . . ,zm Vekto-ren aussagenlogischer Va-riablen, so schreiben wirauch ϕ(~y,~z) anstelle vonϕ(y1, . . . ,yn,z1, . . . ,zm)

• Entsprechend schreiben wir dann~a für eine Folge a1, . . . ,an von

Wahrheitswerten und ϕ(~a,~b) fürden Wahrheitswert von ϕ unterder Belegung

◮ ~y 7→ ~a,

◮ ~z 7→ ~b


Notation





◮ ~y 7→ ~a,

◮ ~z 7→ ~b

• Im folgenden Beweis wird S ein Polynom sein

• Ähnlich wie im Beweis des Satzes von Cook werdenwir Konfigurationen durch Wertebelegungen aussa-genlogischer Variablen kodieren, z.B.:◮ y2,12 7→ 1 falls der Zeiger des 2. Strings an Po-

sition 12 ist◮ y2,12,σ 7→ 1 falls an Position 12 des 2. Strings

ein σ steht


Notation





◮ ~y 7→ ~a,

◮ ~z 7→ ~b

• Im folgenden Beweis wird S ein Polynom sein

• Ähnlich wie im Beweis des Satzes von Cook werdenwir Konfigurationen durch Wertebelegungen aussa-genlogischer Variablen kodieren, z.B.:◮ y2,12 7→ 1 falls der Zeiger des 2. Strings an Po-

sition 12 ist◮ y2,12,σ 7→ 1 falls an Position 12 des 2. Strings

ein σ steht• So lässt sich die Kodierung cs(K) jeder Konfigura-

tionK durch einen Vektor ~a von Wahrheitswertenrepräsentieren (via ~y 7→ ~a)

• Notation:K(~a)def=durch ~a repräsentierte Konfiguration

• Es lässt sich eine quantorenfreie KNF-FormelϕM,S,x(~y,~z) polynomieller Länge (in |x|) konstru-ieren, die die 1-Schritt-Konfigurations-Übergänge be-schreibt• Es sind dann also äquivalent:

◮ K(~a) ⊢M K(~b) und

◮ ϕM,S,x(~a,~b) ist wahr


QBF ist PSPACE-vollständigSatz 2.6

• QBF ist PSPACE-schwierig(also insgesamt PSPACE-vollständig)

Beweisskizze

• Sei L ∈ PSPACE,M TM für L mit Platzschran-ke nℓ, für ein ℓ, und x Eingabe der Länge n

• Idee: Wir konstruieren induktiv QBF-Formelnψi(~y,~z), so dass äquivalent sind:

◮ ψi(~a,~b) = 1

◮ es gibt inGs(M,S,x) einen Weg der Länge

≤ 2i von cs(K(~a)) zu cs(K(~b))




Beweisskizze



◮ ψi(~a,~b) = 1



• Dann sind äquivalent:

◮ x ∈ L◮ ∃~z (ψdnℓ(~s,~z) ∧ χ(~z)) ist wahr, wobei

� der Konstantenvektor ~s die Startkonfigurati-on repräsentiert,

� χ(~z) ausdrückt, dassK(~z) akzeptiert,� und d eine geeignete Konstante ist




Beweisskizze



◮ ψi(~a,~b) = 1








• Klar:ψ0

def= ϕM,S,x(~y,~z) ∨ ~y = ~z

• 1. Versuch für Induktion:

◮ ψi+1(~y,~z)def=

∃~u(ψi(~y,~u) ∧ ψi(~u,~z))




Beweisskizze



◮ ψi(~a,~b) = 1








• Klar:ψ0

def= ϕM,S,x(~y,~z) ∨ ~y = ~z



∃~u(ψi(~y,~u) ∧ ψi(~u,~z))◮ Problem:|ψi+1| ≈

|ψi|+ |ψi| = 2|ψi|

➞ |ψdnℓ| ≈ 2dnℓ




Beweisskizze



◮ ψi(~a,~b) = 1








• Klar:ψ0

def= ϕM,S,x(~y,~z) ∨ ~y = ~z




|ψi|+ |ψi| = 2|ψi|


• Kleiner Trick: Wir definierenψi+1(~y,~z) als:∃~u∀~v∀~w[(~v = ~y ∧ ~w = ~u)∨

(~v = ~u ∧ ~w = ~z)]→ ψi(~v, ~w)




Beweisskizze



◮ ψi(~a,~b) = 1








• Klar:ψ0

def= ϕM,S,x(~y,~z) ∨ ~y = ~z




|ψi|+ |ψi| = 2|ψi|


• Kleiner Trick: Wir definierenψi+1(~y,~z) als:∃~u∀~v∀~w[(~v = ~y ∧ ~w = ~u)∨

(~v = ~u ∧ ~w = ~z)]→ ψi(~v, ~w)

• Dann: |ψi+1| = |ψi|+O(nℓ)

➨ |ψdnℓ| = O(n2ℓ)


Die bisher betrachteten Klassen

P

NP

PSPACE

TILING, SAT

CORRIDORTILING, QBF


Quellen

• Lehrbücher

◮ Papadimitriou. Kapitel 19

◮ Wegener. 13.2, 13.3

◮ Arora, Barak. 4.1, 4.2

◮ Kozen. 8

• Originalarbeiten

◮ QBF ist vollständig für PSPACE:

� L. J. Stockmeyer and A. R. Meyer. Word problems requiringexponential time: Preliminary report. pages 1–9, 1973

◮ NFA-CONTAINMENT ist vollständig für PSPACE:

� Harry B. Hunt III, Daniel J. Rosenkrantz, and Thomas G. Szy-manski. On the equivalence, containment, and covering pro-blems for the regular and context-free languages. J. Comput.

Syst. Sci., 12(2):222–268, 1976


Date post:	08-Aug-2019
Category:	Documents
Upload:	duonghanh
View:	212 times
Download:	0 times

ls1- · Tiling-Puzzle (1/2) •Wir betrachten ein Kachel-Puzzle (englisch für „Kachel“: Tile)...

Documents