Transcript
13.1.2016
Konfiguration von TM M bei Eingabe w und höchstens N Zellen/A-Band Inhalt Eingabeband
Lesekopf Position
Zustand
{w}
× {1,L,|w|} ×
Q
Inhalt der k Arbeitsbänder ×
( ΓN )k
KGM(w,N) Konfigurationsgraph von TM M bei Eingabe w und
×
Sei γ : N → R beliebig langsam wachsend, aber nicht-fallend und limn→∞γ(n) = ∞
höchstens N Zellen/A-Band n=|w|
Positionen der k Lese/Schreibköpfe
Knoten: Kanten:
{1,L,N}k
z.B. γ(n) = log log log log log n
Konfigurationen [C,C’ wenn M in einem Rechenschritt von Konf. C zu Konfig. C’ kommt
Sei f(n) ≥ log2n
Satz A: (Verhältnis zwischen det. Zeit und Platz) DTIME( f(n) ) ⊆ DSPACE( f(n) ) ⊆ DTIME( 2γ(n)f(n) )
KGM(w,N) Konfigurationsgraph von TM M bei Eingabe w und höchstens N Zellen/A-Band
Knoten: Kanten:
Anzahl der Knoten:
Konfigurationen {1,L,|w|}× Q × ( ΓN )k ×{1,L,N}k [C,C’ wenn M in einem Rechenschritt von Konf. C zu Konfig. C’ kommt
Anzahl der Knoten: n·|Q|·|Γ|kN·Nk Anzahl der Kanten: α·n·|Q|·|Γ|kN·Nk
n·|Q|·|Γ|kN·Nk
AN
(falls N≥ log2 n)
A eine von M abh. Konstante
Eingrad und Ausgrad jedes Knoten α
α eine von M abh. Konstante
n=|w|
α eine von M abh. Konstante
13.1.2016
1
13.1.2016
Sei γ : N → R beliebig langsam wachsend, aber nicht-fallend und limn→∞γ(n) = ∞
2
13.1.2016
Sei γ : N → R beliebig langsam wachsend, aber nicht-fallend und limn→∞γ(n) = ∞
Sei f(n) ≥ log2n
Lemma A: (i) L ∈ DTIME( f(n) ) ⇒ L ∈ DSPACE( f(n) )
z.B. γ(n) = log log log log log n
z.B. γ(n) = log log log log log n
(ii) L ∈ DSPACE( f(n) ) ⇒ L ∈ DTIME( Af(n) )
Sei f(n) ≥ log2n
Sei f(n) ≥ log2n
für eine von L abh. Konstante A
Satz A: (Verhältnis zwischen det. Zeit und Platz)
Lemma A: (i) L ∈ DTIME( f(n) ) ⇒ L ∈ DSPACE( f(n) ) (ii) L ∈ DSPACE( f(n) ) ⇒ L ∈ DTIME( Af(n) )
(und so, dass es mit O(f(n)) Platz berechnet werden kann)
Satz B: (Verhältnis zwischen deterministischer und nicht-det. Zeit)
DTIME( f(n) ) ⊆ DSPACE( f(n) ) ⊆ DTIME( 2γ(n)f(n) ) Bew: (i) trivial (ii) M det. TM für L mit Platzverbrauch f(n) w Eingabe für M n=|w|, N=f(n)
3
DTIME( f(n) ) ⊆ NTIME( f(n) ) ⊆ DTIME( 2γ(n)f(n) ) ( ≥ log2 n )
Berechnung von M entspricht Pfad durch KGM(w,N)
für eine von L abh. Konstante A
KGM(w,N) hat höchstens AN Knoten ⇒ M macht auf Eingabe w höchstens AN viele Schritte (sonst Endlosloop ! ) ⇒ M entscheidet L in Zeit Af(n) ⇒ L ∈ DTIME( Af(n) )
13.1.2016
4
13.1.2016
5
13.1.2016
6
1
13.1.2016
Sei f(n) ≥ log2n Sei γ : N → R beliebig langsam wachsend, aber nicht-fallend und limn→∞γ(n) = ∞ Sei f(n) ≥ log2n
Sei γ : N → R beliebig langsam wachsend, aber nicht-fallend und limn→∞γ(n) = ∞
Lemma B: (i) L ∈ DTIME( f(n) ) ⇒ L ∈ NTIME( f(n) ) (ii) L ∈ NTIME( f(n) ) ⇒ L ∈ DTIME( Af(n) )
z.B. γ(n) = log log log log log n
z.B. γ(n) = log log log log log n
Sei f(n) ≥ log2n
für eine von L abh. Konstante A
(und so, dass es mit O(f(n)) Platz berechnet werden kann)
(und so, dass es mit O(f(n)) Platz berechnet werden kann)
Satz C: (Verhältnis zwischen deterministischem und nicht-det. Platz) (Savitch)
Satz B: (Verhältnis zwischen deterministischer und nicht-det. Zeit)
Bew: (i) trivial (ii) M nicht-det. TM für L mit Zeitverbrauch und daher Platzverbrauch f(n) w Eingabe für M n=|w|, N=f(n) ( ≥ log2 n )
DTIME( f(n) ) ⊆ NTIME( f(n) ) ⊆ DTIME( 2γ(n)f(n) ) Lemma B: (i) L ∈ DTIME( f(n) ) ⇒ L ∈ NTIME( f(n) )
DSPACE( f(n) ) ⊆ NSPACE( f(n) ) ⊆ DSPACE( f 2(n) )
Berechnung von M entspricht Pfad durch KGM(w,N) von init(w) zu einer Endkonfiguration
(ii) L ∈ NTIME( f(n) ) ⇒ L ∈ DTIME( Af(n) )
KGM(w,N) hat höchstens AN Knoten und O(AN ) Kanten
für eine von L abh. Konstante A
⇒ det. TM M’ macht Tiefensuche (DFS) in KGM(w,N) und testet, ob eine Endkonfiguration von init(w) erreichbar; braucht Zeit O( # Kanten ) ⇒ M’ entscheidet L in Zeit O(Af(n)) ⇒ L ∈ DTIME( Af(n) )
13.1.2016
7
13.1.2016
Lemma C: (i) L ∈ DSPACE( f(n) ) ⇒ L ∈ NSPACE( f(n) )
Sei γ : N → R beliebig langsam wachsend, aber nicht-fallend und limn→∞γ(n) = ∞
(ii) L ∈ NSPACE( f(n) ) ⇒ L ∈ DSPACE( f(n)2 )
z.B. γ(n) = log log log log log n
Sei f(n) ≥ log2n
8
(und so, dass es mit O(f(n)) Platz berechnet werden kann)
Bew: (i) trivial (ii) M nicht-det. TM für L mit daher Platzverbrauch f(n) w Eingabe für M n=|w|, N=f(n) ( ≥ log2 n
Satz C: (Verhältnis zwischen deterministischem und nicht-det. Platz) (Savitch) DSPACE( f(n) ) ⊆ NSPACE( f(n) ) ⊆ DSPACE( f 2(n) )
13.1.2016
9
Lemma C:
L ∈ NSPACE( f(n) ) ⇒ L ∈ DSPACE( f(n)2 )
Lemma D:
L ∈ NSPACE( f(n) ) ⇒ L ∈ NSPACE( f(n) )
)
Berechnung von M entspricht Pfad durch KGM(w,N) von init(w) zu einer Endkonfiguration
Lemma C: (i) L ∈ DSPACE( f(n) ) ⇒ L ∈ NSPACE( f(n) )
KGM(w,N) hat höchstens AN Knoten und O(AN ) Kanten (A konstant)
(ii) L ∈ NSPACE( f(n) ) ⇒ L ∈ DSPACE( f(n)2 )
Daher ist die Darstellungsgröße von Knoten O(log AN) = O(N·log A) = O(f(n)) ⇒ Brauche det. TM M’ (deterministischen Algorithmus) zum Testen, ob in KGM(w,N) eine Endkonfiguration von init(w) erreichbar ist;
Dieser Algorithmus soll wenig Platz brauchen !! 13.1.2016
10
13.1.2016
11
13.1.2016
12
2
13.1.2016
Lemma C: Lemma D:
Abstraktes Problem:
L ∈ NSPACE( f(n) ) ⇒ L ∈ DSPACE( f(n)2 )
Für Beweis von Lemma C, deterministische Lösung mit O(log2|V|) Platzverbrauch
Gerichteter Graph G = (V,E) ist implizit gegeben, d.h. man kann (i) die Knoten in V aufzählen (ii) für zwei Knoten u,v testen, ob u=v (iii) für zwei Knoten u,v testen, ob [u,v ∈ E und zwar jeweils mit Speicherverbrauch O(log |V|) (Knotendarstel-
L ∈ NSPACE( f(n) ) ⇒ L ∈ NSPACE( f(n) )
Der Beweis reduziert sich auf “Berechnen” von Erreichbarkeit in einem sehr großen, implizit gegebenen Graphen. Es muss die Frage beantwortet werden
erreichbar( s , v, λ ) = if λ =0 then return (s=v) if λ =1 then return (s=v) or [s,v∈E else for each m∈V do if erreichbar( s , m , ⌊λ/2⌋ ) and erreichbar( m , v ,⌈λ /2⌉ ) then return true endfor return false
lungsgröße)
Berechne
∃ gerichteter Pfad von startw zu einer Endkonfiguration im Konfigurationsgraphen KGM(w,N)
erreichbar( s , v, λ ) . . . gibt es in G einen gerichteten Pfad von s nach v der Länge höchstens λ ?
n=|w| N=f(n)
Laufzeit: O((log λ)· Darstellungsgröße(v) ) = O (log2|V|) mit λ=|V| 13.1.2016
13
13.1.2016
14
13.1.2016
15
3
