anim

Transcrição

anim

Theoretische Informatik II
Einheit 5.4
Hierarchie von Komplexitätsklassen
1. Komplementäre Klassen
2. Polynomieller Platz
3. Logarithmischer Platz
4. Hierarchiesätze
Es gibt weitere wichtige Komplexitätsklassen
• co−N P
– Probleme mit Komplement in N P
– Problem muß nicht notwendigerweise selbst in N P liegen
Theoretische Informatik II §5.4:
1
• co−N P
p
p
• Σi / Π i
– Σp2: Sprachen von OTMs, deren Orakel ein N P-Problem entscheidet
– Πp2 : Sprachen von OTMs, deren Orakel ein co−N P-Problem entscheidet
1
• co−N P
p
p
• Σi / Π i
• P SP ACE
– Platzverbrauch polynomiell relativ zur Größe der Eingabe
1
• co−N P
p
p
• Σi / Π i
• P SP ACE
• LOGSP ACE
– Platzverbrauch der Berechnung logarithmisch in Größe der Eingabe
1
• co−N P
p
p
• Σi / Π i
• P SP ACE
• LOGSP ACE
– Platzverbrauch der Berechnung logarithmisch in Größe der Eingabe
• EXP T IM E / EXP SP ACE
– Rechenzeit und Platzverbrauch werden nicht mehr handhabbar
1
co−N P : Probleme mit Komplement in N P
co−C := { L | L ∈ C }
2
co−C := { L | L ∈ C }
• Interessant für nichtdeterministische Klassen
2
co−C := { L | L ∈ C }
– Für deterministische Komplexitätsklassen gilt C = co−C
Akzeptieren/Verwerfen einer DTM ist vertauschbar
2
co−C := { L | L ∈ C }
– Nichtdeterministisches Akzeptieren ist komplizierter:
OTM akzeptiert, wenn Orakel einen akzeptablen Lösungsvorschlag machen kann
2
co−C := { L | L ∈ C }
• Beispiele für Probleme in co−N P:
2
co−C := { L | L ∈ C }
– Menge der allgemeingültigen Formeln (Komplement von SAT )
2
co−C := { L | L ∈ C }
– Das Primzahlproblem (Komplement von Zusammengesetztheit)
2
co−C := { L | L ∈ C }
• Es gibt Probleme in N P ∩ co−N P
2
co−C := { L | L ∈ C }
– Das Primzahlproblem liegt auch in N P
2
HMU, Satz 11.26
co−C := { L | L ∈ C }
Mittlerweile ist PRIMES ∈ P bekannt
2
HMU, Satz 11.26
(Gilt N P ∩ co−N P = P ?)
co−C := { L | L ∈ C }
HMU, Satz 11.26
• Sehr wahrscheinlich gilt co−N P6=N P
2
co−C := { L | L ∈ C }
HMU, Satz 11.26
– Wenn P = N P, dann co−N P = co−P = P = N P P = N P
2
co−C := { L | L ∈ C }
HMU, Satz 11.26
– N P = co−N P ⇔ N PC ∩ co−N P6=∅
2
co−C := { L | L ∈ C }
HMU, Satz 11.26
– N P = co−N P ⇔ N PC ∩ co−N P6=∅
⇒ : offensichtlich, da N PC6=∅
⇐ : Ist L ∈ N PC ∩ co−N P so gilt L′≤p L für jedes L′ ∈ co−N P also L′≤pL ∈ N P
2
P SP ACE : Polynomieller Platzverbrauch
• N P ⊆ P SP ACE
– Eine Maschine kann in polynomieller Zeit nur polynomiell viele
Speicherzellen verwenden
3
• N SP ACE(f (n))⊆SP ACE(f (n)2 )
(Satz von Savitch)
3
(Satz von Savitch)
– Simulation mit Speicherung der Alternativen (§4.1) zu platzaufwendig
3
(Satz von Savitch)
– Simulation mit Speicherung der Alternativen (§4.1) zu platzaufwendig
– Teste κα ⊢t κω (für maximales t=2c∗f (n)) durch “binäre Tiefensuche”
3
(Satz von Savitch)
–
–
–
–
Simulation mit Speicherung der Alternativen (§4.1) zu platzaufwendig
Teste κα ⊢t κω (für maximales t=2c∗f (n)) durch “binäre Tiefensuche”
Platzverbrauch des Rekursionsstacks ist O(f (n)2)
(falls f (n)≥log n)
Zeitaufwand der Simulation ist exponentiell höher als bei der NTM
3
(Satz von Savitch)
–
–
–
–
• P SP ACE = N P SP ACE
HMU §11.2.3
– Folgt direkt aus dem Satz von Savitch
3
(Satz von Savitch)
–
–
–
–
HMU §11.2.3
• P SP ACE ⊆ EXP T IM E
3
(Satz von Savitch)
–
–
–
–
HMU §11.2.3
– Eine terminierende Maschine, die maximal f (n) Bandzellen aufsucht,
terminiert nach maximal c1+f (n) Schritten
– Für |Γ| + |Q| = c sind maximal c1+f (n) Konfigurationen möglich
3
(Satz von Savitch)
–
–
–
–
HMU §11.2.3
– Eine terminierende Maschine, die maximal f (n) Bandzellen aufsucht,
terminiert nach maximal c1+f (n) Schritten
– Für |Γ| + |Q| = c sind maximal c1+f (n) Konfigurationen möglich
N P SP ACE ⊆ N EXP T IM E gilt aus dem gleichen Grund
3
P SP ACE -Vollständigkeit
• C-Vollständigkeit allgemein
– L ist C-vollständig, falls L ∈ C und L′≤pL für alle L′ ∈ C
4
• Wie zeigt man P SP ACE-Vollständigkeit?
– Codiere Berechnungen von DTMs, die polynomiellen Platz brauchen
– Sprache: komplexer als SAT , aber mit deterministischer Natur
4
– Kandidat: Wahrheit geschlossener quantifizierter boolescher Formeln
4
• Erweitere Aussagenlogik um boolesche Quantoren
– Ausagenlogische Variablen P, Q, R, ..., Konstante t und f
– Formeln ¬F , E ∧ F , E ∨ F , E ⇒ F , (∀P )F , (∃P )F
4
–
–
–
–
–
Ausagenlogische Variablen P, Q, R, ..., Konstante t und f
Formeln ¬F , E ∧ F , E ∨ F , E ⇒ F , (∀P )F , (∃P )F
Wert von (∀P )F entspricht dem von F [t/P ] ∧ F [f /P ]
Wert von (∃P )F entspricht dem von F [t/P ] ∨ F [f /P ]
Wert anderer Formeln wie in gewöhnlicher Aussagenlogik
4
–
–
–
–
–
(∀P )(∃Q) [(P ∨ Q) ∧ (¬P ∨ ¬Q)] ist wahr (Wert 1)
(∃Q)(∀P ) [(P ∨ Q) ∧ (¬P ∨ ¬Q)] ist falsch (Wert 0)
4
–
–
–
–
–
(∀P )(∃Q) [(P ∨ Q) ∧ (¬P ∨ ¬Q)] ist wahr (Wert 1)
(∃Q)(∀P ) [(P ∨ Q) ∧ (¬P ∨ ¬Q)] ist falsch (Wert 0)
QBF ist die Menge der geschlossenen QB-Formeln mit Wert 1
4
QBF ist P SP ACE -vollständig
• QBF ∈ P SP ACE
– Auswerten aussagenlogischer Formeln braucht linearen Platz
– (∀P )F = F [t/P ] ∧ F [f /P ] und (∃P )F = F [t/P ] ∨ F [f /P ]
werden kaskadisch ausgewertet
5
– Gesamtbedarf, einschließlich Zwischenspeicherung, ist quadratisch
5
• Für alle L ∈ P SP ACE gilt L≤pQBF
HMU §11.3.4
– Codiere Bandzellen und Konfigurationen wie im Satz von Cook
5
HMU §11.3.4
– Beschreibe Formeln Fκ1,κ2,t für die Aussage κ1 ⊢t κ2
5
HMU §11.3.4
– Zielformel ist Fκα ,κω ,2c∗p(n) , wobei κα Anfangskonfiguration,
κω Endkonfiguration, p(n) Platzverbrauch, c Alternativen pro Zelle
5
HMU §11.3.4
– Setze Fκ1 ,κ1,0 und beschreibe Fκ1,κ2,1 passend zur Tabelle von δ
5
HMU §11.3.4
– Setze Fκ1 ,κ1,0 und beschreibe Fκ1,κ2,1 passend zur Tabelle von δ
– Beschreibe Fκ1,κ2,t durch eine Darstellung für (∃κ)Fκ1 ,κ,t÷2 ∧ Fκ,κ2,t÷2,
die das Entstehen exponentiell großer Formeln vermeidet
(∃κ)(∀κ3)(∀κ4)[(κ3 ⇔ κ1 ∧ κ4 ⇔ κ) ∨ (κ3 ⇔ κ ∧ κ4 ⇔ κ2)] ⇒ Fκ3,κ4,t÷2
5
Weitere P SP ACE -vollständige Probleme
• Strategische 2-Personen Spiele
– Viele konkrete Beispiele in Garey/Johnson Seite 254ff
6
– Spielentscheidungen entsprechen alternierenden QB Formeln
Spieler gewinnt, wenn für jeden Zug des Gegners, ein Zug existiert, so
daß für jeden Folgezug des Gegners, ... das Resultat einen Sieg darstellt
6
– QBF kann als strategisches Spiel beschrieben werden (und umgekehrt)
6
• Sprache regulärer Ausdrücke
– Ist L(E) = Σ∗ für einen beliebigen regulären Ausdruck über Σ?
6
• Sprache regulärer Ausdrücke
– Ist L(E) = Σ∗ für einen beliebigen regulären Ausdruck über Σ?
• In-Place Acceptance
Asteroth/Baier §4.5
– Kann eine gegebene DTM jedes Wort w ihrer Sprache mit
Platzbedarf |w| akzeptieren?
6
LOGSP ACE Logarithmischer Platzverbrauch
• LOGSP ACE ⊆ P
– Gleiches Argument wie bei P SP ACE
7
⊆
EXP T IM E
• LOGSP ACE ⊆ P
⊆
EXP T IM E
?
• LOGSP ACE = N LOGSP ACE ist ungeklärt
– Analyse benötigt Begriff der log-space Reduzierbarkeit
7
• LOGSP ACE ⊆ P
⊆
EXP T IM E
?
• Es gibt N LOGSP ACE-vollständige Probleme
Sipser Satz 8.20
– P AT H = { (G, v, v ′) | G=(V, E) gerichteter Graph
′
∧ ∃{v = v1, .., vn=v }⊆V. v1 ..vn Pfad in G }
7
• LOGSP ACE ⊆ P
⊆
EXP T IM E
?
Sipser Satz 8.20
′
• N LOGSP ACE ⊆ P
Sipser Korollar 8.21
– P AT H ist in polynomieller Zeit lösbar
7
• LOGSP ACE ⊆ P
⊆
EXP T IM E
?
Sipser Satz 8.20
′
• N LOGSP ACE ⊆ P
Sipser Korollar 8.21
– P AT H ist in polynomieller Zeit lösbar
• N LOGSP ACE = co−N LOGSP ACE
Sipser Satz 8.22
– P AT H liegt auch in N LOGSP ACE
7
Wichtige Vertreter weiterer Komplexitätsklassen
• Isomorphie ungerichteter Graphen
8
N P, nicht vollständig
• Zuverlässigkeit von Netzwerken
N P-hart, vermutlich nicht in N P
– Wahrscheinlichkeit für fehlerfreie Verbindung zwischen zwei Knoten
8
• Minimale äquivalente Schaltkreise
N P-hart, nicht in N P (“Σp2 ”)
– Bestimme optimale Größe einer Schaltung
8
• TSP∗: Bestimmung aller Rundreisen mit gegebenen Kosten
– Unrealistische Problemstellung: zu viele Lösungen
8
EXP SP ACE
• TSP∗: Bestimmung aller Rundreisen mit gegebenen Kosten
– Unrealistische Problemstellung: zu viele Lösungen
EXP SP ACE
• Äquivalenz regulärer Ausdrücke mit Iteration
– Einfache Problemstellung mit sehr schwieriger Lösung
– Ausdrücke dürfen E k = E
| ◦E...
{z ◦E} enthalten EXP SP ACE-vollständig
k−mal
8
Bedeutet mehr Zeit/Platz auch mehr lösbare Probleme?
• Welche der folgenden Inklusionen sind echt?
⊆
⊆
LOGSP ACE ⊆ N LOGSP ACE
P ⊆ N P ⊆ P SP ACE = N P SP ACE
EXP T IM E ⊆ N EXP T IM E ⊆ EXP SP ACE
9
⊆
...
⊆
⊆
⊆
...
• Wie beweist man Unlösbarkeit in Platz/Zeit f
– Diagonalisierung über alle Probleme, die in Komplexität f lösbar sind
9
⊆
⊆
⊆
...
• Hilfsmittel: Konstruierbare Funktionen
– Funktionen, deren Komplexität durch ihren Wert beschränkt ist
9
⊆
⊆
⊆
...
– f : N→N ist platzkonstruierbar, wenn fˆ in Platz O(f ) berechenbar
– f : N→N ist zeitkonstruierbar, wenn fˆ in Zeit O(f ) berechenbar
fˆ:{1}∗→{0, 1, }∗ berechnet bei Eingabe 1n die Binärdarstellung rb (f (n)) von f (n)
Rahmenbedingungen: f (n)≥ log n (Platz) bzw. f (n)≥n log n (Zeit) für alle n
9
⊆
⊆
⊆
...
– log n, nk , 2n etc sind zeit- und platzkonstruierbar
9
⊆
⊆
⊆
...
– log n, nk , 2n etc sind zeit- und platzkonstruierbar
• Wichtiger formaler Begriff: Ordnung o(f )
– f als echte obere Schranke: o(f ) = {g:N→R+| ∀c>0. g <a c∗f }
9
Das Platzhierarchie-Theorem
Für jede platzkonstruierbare Funktion f gibt es ein
L ∈ SP ACE(f ) mit Platzkomplexität nicht in o(f )
10
• Konstruiere L durch Diagonalisierung
– Definiere L durch seine charakteristische Funktion
10
1 Φi(n)≤2f (n) ∧ sMi (n)≤∗∗f (n) ∧ ϕi(n)=0 mit i = π1(n)
– Sei h(n) =
0 sonst
sMi (n)≤∗∗f (n) ≡ h benutzt zur Simulation von ϕi(n) maximal Platz f (n).
Benutzt die Simulation von ϕi(n) Platz d∗sMi (n), so muß sMi (n)≤f (n)/d gelten
10
– Sei h(n) =
0 sonst
– h ist eine Entscheidungsfunktion, die in Platz O(f ) berechenbar ist
– Definiere L := h−1({1}) (also χL = h), also L ∈ SP ACE(f )
10
– Sei h(n) =
0 sonst
• Die Platzkomplexität von L ist nicht in o(f )
– Falls L durch ein Programm mit Komplexität o(f ) entschieden wird,
so gilt χL =ϕk für ein k mit sMk (n)<c∗f (n) für alle c>0, n≥n0
10
– Sei h(n) =
0 sonst
– Wähle n := hk, n0i (also k=π1(n)) für das zu (1/d) passende n0
Dann gilt n≥n0, also sMk (n)<(1/d)∗f (n) bzw sMi (n)≤∗∗f (n)
10
– Sei h(n) =
0 sonst
– Wähle n := hk, n0i (also k=π1(n)) für das zu (1/d) passende n0
Dann gilt n≥n0, also sMk (n)<(1/d)∗f (n) bzw sMi (n)≤∗∗f (n)
– Es folgt n ∈ L ⇔ h(n)=1 ⇔ ϕk (n)=0 ∧ sMi (n)≤∗∗f (n) ⇔ n 6∈ L
10
Konsequenzen des Hierarchietheorems
• Platzkomplexität bildet eine echte Hierarchie
11
– SP ACE(f )⊂SP ACE(g) falls g platzkonstruierbar und f ∈ o(g)
11
′
– SP ACE(nǫ)⊂SP ACE(nǫ ) für alle 0≤ǫ<ǫ’
11
′
– N LOGSP ACE ⊆ SP ACE(log2 n) ⊂ SP ACE(n) ⊂ P SP ACE
– N P SP ACE ⊂EXP SP ACE
11
′
• Zeitkomplexität bildet eine echte Hierarchie
11
′
– Für jede zeitkonstruierbare Funktion f gibt es ein
L ∈ T IM E(f ) mit Zeitkomplexität nicht in o(f / log f )
· Beweis analog zu Platzhierarchietheorem
11
′
– T IM E(f )⊂T IM E(g) falls g platzkonstruierbar und f ∈ o(g/ log g)
′
– T IM E(nǫ)⊂T IM E(nǫ ) für alle 0≤ǫ<ǫ’
11
′
– T IM E(f )⊂T IM E(g) falls g platzkonstruierbar und f ∈ o(g/ log g)
′
– T IM E(nǫ)⊂T IM E(nǫ ) für alle 0≤ǫ<ǫ’
– P ⊂EXP T IM E
11
Komplexitätsklassenhierarchie
EXPSPACE
PTI
X
E
N
EXPTIME
ME
PSPACE = NPSPACE
NP
co−NP
NPC
LOGSPACE
P
NLOGSPACE
12

anim

Transcrição

Documentos relacionados

du bist so gut wie dein material. wenn dein material so gut ist wie du.

Ich möchte meine ACE-Mitgliedschaft mit dem ACE Reise

für Single für jährlich ................................................14,50 € für Familie

Samsung Galaxy Ace S5830

Kleine Tipps für großen Malspaß! Space+

Mobilität in Sachsen-Anhalt Verkehrspolitische Forderungen

Binter Canarias, ATR 72-202

FSU Simu. Interface, 9C Stecker

Unsere aktuellen Angebote!

Edital II - 1º Registro Joinville