Lösung 8

Theoretische Informatik
Departement Informatik
Prof. Dr. Juraj Hromkovič
Prof. Dr. Emo Welzl
http://www.ita.inf.ethz.ch/theoInf15
Lösungsvorschläge – Blatt 8
Zürich, 27. November 2015
Lösung zu Aufgabe 22
Sei f : N → N eine monoton steigende Funktion mit f (n) ≥ n für alle n ∈ N.
(a) Seien L1 , L2 ∈ NTIME(f ). Wir wollen zeigen, dass dann auch L1 ∪ L2 ∈ NTIME(f )
gilt. Nach der Definition von NTIME(f ) existieren also zwei nichtdeterministische
Mehrband-Turingmaschinen M1 mit k1 Bändern und M2 mit k2 Bändern für k1 , k2 ≥
1, so dass L1 = L(M1 ), L2 = L(M2 ) und TimeM1 (w), TimeM2 (w) ∈ O(f (n)) für
alle Eingaben w der Länge n. Wir konstruieren hieraus eine nichtdeterministische
(k1 + k2 + 1)-Band TM M für L = L1 ∪ L2 wie folgt.
Die Maschine M kopiert zunächst ihre Eingabe auf das erste Arbeitsband und fährt
dann die Köpfe auf den Bändern wieder zurück an den Anfang. Dies ist offenbar in
Zeit O(n) möglich, und damit auch in O(f (n)), da f (n) ≥ n gilt für alle n ∈ N.
Nun simuliert M parallel die Arbeit von M1 auf dem Eingabeband und den Arbeitsbändern 2 bis k1 + 1 und die Arbeit von M2 mit Arbeitsband 1 als Eingabeband
und mit den Arbeitsbändern k1 + 2 bis k1 + k2 + 1. Die Maschine M akzeptiert
nun genau dann, wenn mindestens eine der beiden Simulationen von M1 und M2
akzeptiert. Offenbar gibt es eine akzeptierende Berechnung von M auf dem Wort
w genau dann, wenn es akzeptierende Berechnungen von M1 oder von M2 auf
w gibt. Weiterhin ist die kürzeste akzeptierende Berechnung von M auf w nicht
länger als die kürzeste akzeptierende Berechnung von M1 oder M2 auf w. Damit gilt TimeM (w) = O(n) + min{TimeM1 (w), TimeM2 (w)} ∈ O(f (n)). Also folgt
L1 ∪ L2 ∈ NTIME(f ).
(b) Seien L ∈ NTIME(f ) und L0 ∈ TIME(f ). Dann existieren eine nichtdeterministische
k1 -Band-Turingmaschine M1 für L und eine deterministische k2 -Band-Turingmaschine
M2 für L0 mit TimeM1 (n), TimeM2 (n) ∈ O(f (n)). Wir konstruieren hieraus eine
nichtdeterministische (k1 + k2 )-Band-TM M für L − L0 mit O(f (n)) Zeitbedarf wie
folgt.
Zunächst simuliert M die Arbeit von M2 auf der Eingabe w der Länge n auf den
Arbeitsbändern k1 + 1 bis k1 + k2 . Falls M2 den akzeptierenden Zustand erreicht
hat, dann gilt w ∈ L0 , also w ∈
/ L − L0 , also verwirft M die Eingabe. Falls M2 den
verwerfenden Zustand erreicht, dann gilt w ∈
/ L0 . In diesem Fall setzt M den Lesekopf
auf dem Eingabeband zurück an den Anfang und startet eine Simulation von M1 auf
w auf den ersten k1 Arbeitsbändern. Falls M1 das Wort w akzeptiert, dann akzeptiert
auch M .
Die Zeitkomplexität von M lässt sich wie folgt abschätzen. Die Simulation von
M2 benötigt offenbar O(f (n)) Schritte, das Zurücksetzen des Lesekopfes dann noch
einmal höchstens O(f (n)) Schritte. Wenn das Wort w von M1 akzeptiert wird, gibt es
nach Definition der nichtdeterministischen Zeitkomplexität auch eine Berechnung, in
der die Simulation von M1 in O(f (n)) Zeit durchgeführt wird. Also gilt TimeM (n) ∈
O(f (n)).
Lösung zu Aufgabe 23
(a) Sei M eine nichtdeterministische MTM mit TimeM (n) ∈ O(n2 ) und die ausserdem die Platzschranke O(n) auf jeder Berechnung einhält. Um zu zeigen, dass
L(M ) ∈ SPACE(n log n) gilt, konstruieren wir eine deterministische MTM A mit
L(A) = L(M ), die die Berechnungen von M simuliert. Für die Konstruktion orientieren wir uns am Beweis des Satzes von Savitch aus dem Buch. Wir nehmen also
wieder an, dass M für alle Wörter w ∈ L(M ) nur eine eindeutige akzeptierende
Konfiguration besitzt, so dass die deterministische Simulation der Arbeit von M , die
A durchführt, nur feststellen muss, ob die akzeptierende Konfiguration Caccept (w)
von der Startkonfiguration Cstart aus erreichbar ist. Wegen der Voraussetzung über
die Zeitkomplexität von M kann eine kürzeste akzeptierende Berechnung von M auf
w höchstens die Länge d · |w|2 haben für eine geeignete Konstante d. Um festzustellen,
ob Caccept (w) aus Cstart in d · |w|2 Schritten erreichbar ist, verwenden wir dieselbe
Prozedur REACHABLE wie im Beweis des Satzes von Savitch. Weil die Funktion
log2 (d · n2 ) = 2 log2 n + log2 d offenbar platzkonstruierbar ist, kann A den Wert
d · |w|2 für jedes beliebige Wort ausrechnen und in 2 log2 |w| + log2 d Speicherplatz
abspeichern. Jede innere Konfiguration einer Berechnung von M auf w kann in c · |w|
Platz gespeichert werden, weil nach Voraussetzung jede Berechnung mit O(n) Platz
auskommt. Bei der Durchführung von REACHABLE müssen höchstens O(log2 |w|)
Konfigurationen auf einmal gespeichert werden, weil die Rekursionstiefe logarithmisch
in der Zeitkomplexität von M ist. Damit ergibt sich mit derselben Argumentation
wie im Beweis des Satzes von Savitch ein Platzbedarf in O(|w| · log |w|) für A.
(b) Eine ähnliche Konstruktion wie im Aufgabenteil (a) oder im Beweis des Satzes von Savitch funktioniert hier nicht. Für jede Sprache L in NSPACE(f (n)) ∩ NTIME(f (n)k )
gilt L ∈ NSPACE(f (n)) und L ∈ NTIME(f (n)k ). Also gibt es eine nichtdeterministische MTM M1 mit L(M1 ) = L und SpaceM1 (n) ∈ O(f (n)) und eine nichtdeterministische MTM M2 mit L(M2 ) = L und TimeM2 (n) ∈ O((f (n))k ). Es kann also sein,
dass es eine MTM gibt, die L mit kleiner Platzkomplexität entscheidet, und eine
andere MTM, die L mit geringer Zeitkomplexität entscheidet. Um einen Beweis wie
in Aufgabenteil (a) führen zu können, brauchen wir aber eine nichtdeterministische
MTM, die beide Schranken für Platz und Zeit einhält.
Lösung zu Aufgabe 24
Sei L ∈ VP, sei A ein Polynomialzeit-Verifizierer für L. Es gelte, dass für jedes Wort w ∈ L
ein Zeuge x mit |x| ≤ log2 |w| existiert, so dass A die Eingabe (w, x) akzeptiert.
Die folgende Turingmaschine M entscheidet L: Für alle Zeugen x ∈ Σ∗bool mit |x| ≤ log2 |w|
simuliert M nacheinander die Arbeit von A auf (w, x). Falls A ein Paar (w, x) akzeptiert,
dann akzeptiert auch M . Falls A jedes Paar (w, x) verwirft, dann verwirft auch M .
Wir zeigen zunächst L(M ) = L. Wenn w ∈ L, dann existiert nach Voraussetzung ein
Zeuge x ∈ Σ∗bool mit |x| ≤ log2 |w|, so dass (w, x) von A akzeptiert wird. Dieser Zeuge wird
auch von M in einer ihrer Simulationen untersucht, also akzeptiert M in dieser Simulation.
Damit gilt w ∈ L(M ).
Wenn w ∈ L(M ), dann hat M in einer ihrer Simulationen ihre Eingabe akzeptiert. Dies
geschieht aber nur dann, wenn für den in dieser Simulation verwendeten Zeugen x der
Verifizierer A die Eingabe (w, x) akzeptiert hat. Damit ist die Bedingung für w ∈ L erfüllt.
Nun zeigen wir, dass M in Polynomzeit läuft. Da A ein Polynomialzeit-Verifizierer ist,
existiert ein Polynom p mit TimeA (w, x) ≤ p(|w|) für alle x ∈ Σ∗bool . Die Laufzeit einer
Simulation von M ist also beschränkt durch p(|w|) + c für eine Konstante c. Der konstante
Zusatzaufwand ergibt sich daraus, dass M die Zeugen generieren muss. Bei einer geschickten
Aufzählung der Zeugen ist dies mit konstantem Aufwand pro Simulation möglich.
Es ergibt sich als Anzahl der Zeugen x ∈ Σ∗bool mit |x| ≤ log2 |w|:
blog2 |w|c
X
2i = 2blog2 |w|c+1 − 1 < 2blog2 |w|c+1 ≤ 2|w|.
i=0
Die Anzahl der Zeugen x ∈ Σ∗bool mit |x| ≤ log2 |w| ist aber gerade die maximale Anzahl
der Simulationen, die M durchführt, also folgt insgesamt für zwei Konstanten c und d,
dass
TimeM (w) ≤ 2|w| · (p(|w|) + c) + d ∈ O(|w|p(|w|)).
Damit ist M eine deterministische Polynomialzeit-TM, die L entscheidet, also L ∈ P.

Download Report