Kapitel 7 - Informatik - FB3

Komplexitätstheorie
Kapitel 7: Orakel
Einleitung
Ein Gedankenexperiment:
• Nimm an, Programm A rufe Unterprogramme B1,...,Bn auf
• Wir haben ein Orakel, das wir nach den Bi befragen können
• Orakelantwort kommt nach 1 Schritt zurück (ohne extra Speicherbedarf)
Ermöglicht Analyse der Kosten für A relativ zu den Kosten der Bi
Orakel erlauben feinere Komplexitätsanalyse mancher Probleme:
• Struktur der Standard-Komplexitätsklassen wird verfeinert
• Einige Orakelklassen haben natürliche vollständige Probleme
Orakel haben wie Nichtdeterminismus theoretischen Charakter
2
Kapitel 7
Die Polynomielle Hierarchie (PH)
3
PH
(N)LogSpace, NC, AC, etc: reiche Struktur innerhalb von P
Die polynomielle Hierarchie liefert Struktur zwischen P und PSpace
Wichtiges Problem für Schaltkreisentwurf:
Definition Minimal Circuit (MC)
Schaltkreis C ist minimal wenn |C | |C| für alle C , die äquivalent zu C
sind, also gleiche Anzahl n von Eingabebits und
C(w) = C (w) für alle w ⇥ {0, 1}n
MC ist Menge aller minimalen Schaltkreise.
Was ist die ”richtige” Komplexitätsklasse (Vollständigkeit!) für dieses
Problem?
4
PH
Offensichtliches “Teilproblem” ist CEQ := {(C, C ) | C äquivalent zu C }
Lemma
CEQ ist co-NP-vollständig.
Betrachte wieder MC:
• Ist in NP wenn wir einen CEQ-Algorithmus als Unterprozedur
ohne Zeitverbrauch verwenden
• Wir können beide Algorithmen nicht zu einem NP-Algorithmus
vereinigen, weil der NP-Algorithmus einen co-NP-Algorithmus aufruft
(⇤⇥-Charakteristik)
Derartige Probleme sind offensichtlich in PSpace. Man kann deren
Komplexität aber noch exakter bestimmen
5
Orakel
Orakel: Unterprogramm, dessen Zeitverbrauch ausgeblendet wird,
dargestellt als formale Sprache
Definition Orakel-TM
Eine Orakel-TM (OTM) M O ist eine (deterministische oder nicht-deterministische) TM M ausgestattet mit einem Orakel O ⇥ ⇥ . OTM hat
• ein zusätzliches Orakelband
• drei spezielle Zustände q? , q+ , q .
Für q+ und q sind normale Transitionen definiert. Der Folgezustand
von q? ist q+ wenn das momentane Wort auf dem Orakelband in O ist
und q sonst. Kopfposition und Bandinhalte bleiben dabei unverändert.
Also schon gesehen: MC wird von Polyzeit-beschränkter ONTM akzeptiert
wenn O=CEQ
6
Orakel
Orakel-TM ist ebensowenig realistisches Berechnungsmodell wie
nicht-deterministische TMs
Dennoch können mittels Orakel-TMs natürliche Komplexitätsklassen
definiert werden (natürlich = erfassen viele natürliche Probleme)
Orakel-TMs können auch verwendet werden, um komplexitätstheoretische Annahmen zu formalisieren, z.B.:
• wenn SAT in konstanter Zeit lösbar wäre, welche anderen Probleme
wären dann effizient lösbar (in Polyzeit mit SAT-Orakel)?
• wenn das Halteproblem für Turingmaschinen H entscheidbar wäre,
welche anderen Probleme wären dann entscheidbar
(von TM mit H-Orakel)
7
Orakel
Definition Orakel-Komplexitätsklassen
Sei O ⇥
ein Orakel. Dann:
• PO := {L | L wird von ODTM M O in poly-Zeit entschieden }
• NPO := {L | L wird von ONTM M O in poly-Zeit entschieden }
Sei C Komplexitätsklasse. Dann:
P :=
C
O
P
NP :=
O⇥C
Schon gezeigt: MC
C
NPCEQ , also in MC
NP
O
O⇥C
NPco-NP
Leicht zu sehen: NPco-NP = NP NP
8
PH
Einige Beispiele:
• PP = P, NPP = NP;
(Integriere Orakel in OTM)
• NP
NP
= NP ist hingegen nicht klar, denn co-NP ✓ P
co-NP
=P
NP
✓ NP
NP
• PNP = PSAT und ebenso für jedes andere NP-vollständige Problem
(Genügt zu zeigen: PO ✓ PSAT mit O 2 NP
integriere dazu Reduktion O p SAT in OTM)
co-NPC verwenden wir für NPC
9
PH: Definition
Die polynomielle Hierarchie entsteht nun durch iteriertes Orakelanwenden
Definition Polynomielle Hierarchie
•
p
1
= P, ⌃p1 = NP, ⇧p1 = co-NP,
• Für k
1 sei
–
p
k+1
–
⌃pk+1
⇧pk+1
–
=P
⌃p
k
= NP
⌃p
k
= co-⌃pk+1
10
PH: Bild und einfache Eigenschaften
..
.
p
3
p
2
= NP NP
p
2
p
2
p
1
=P
NP NP
Echtheit der
Inklusionen ist
unbekannt.
= PNP
p
1
= NP
p
1
= co-NP NP
= co-NP
=P
Lemma
Für alle k ⇥ 1 gilt:
p
k
⇤pk
p
k+1
und
p
k
⇥pk
p
k+1
11
Die Klasse PH
Es gibt auch eine Klasse für die gesamte polynomielle Hierarchie:
Definition Polynomielle Hierarchie
PH =
k 1
p
k
Die polynomielle Hierarchie liegt zwischen P und PSpace:
Theorem
PH
PS PACE
12
Kollaps der PH
Viele Resultate in der Komplexitätstheorie beziehen sich auf die
Echtheit der Inklusionen in der polynomiellen Hierarchie
Die polynomielle Hierarchie kollabiert wenn PH =
p
k
für ein k
1
Lemma
Wenn
Also:
p
k
=
p
k 1
=
p
k+1 ,
p
k
dann PH =
p
k.
schwächere Annahme als
p
k
=
p
k+1
und P = NP schwächste aller dieser Annahmen
Anders formuliert: PH kollabiert am ehesten weit oben!
Theorem
Wenn PH = PS PACE, dann kollabiert PH.
13
Eine nützliche Eigenschaft
Eine Aussage über eingeschränkte Interaktion mit dem Orakel
Lemma
Sei M O eine Polyzeit-ONTM mit Orakel O 2 ⌃pk mit q+ = qacc
(d. h.: M O akzeptiert, sobald eine Orakelfrage positiv beantwortet wird).
Dann gilt: L(M O ) 2 ⌃pk .
Idee:
• rate Orakelantworten im Voraus
• integriere O-Berechnung – verwirf bei abweichenden Antworten sofort
Analoge Aussage per Komplementierung:
Lemma
Sei M O eine Polyzeit-ONTM mit Orakel O 2 ⇧pk mit q = qrej .
Dann gilt: L(M O ) 2 ⇧pk .
14
Kapitel 7
Logische Charakterisierung der Polynomiellen Hierarchie
15
Charakterisierung PH
Zur Erinnerung: L 2 NP gdw.
es gibt Polynom q und L0 2 P mit L = {w | 9u 2 {0, 1}q(|w|) : (w, u) 2 L0 }.
Folgende Charakterisierung generalisiert Definition von NP
Theorem
L 2 ⌃pk gdw. es Polynom q und L0 2 P gibt, so dass
L = {w | 9u1 2 A . 8u2 2 A . 9u3 2 A . . . Quk 2 A : (w, u1 , . . . , uk ) 2 L0 },
wobei A = {0, 1}q(|w|) und Q der sich durch Alternierung ergebende Quantor.
Die Klassen der polynomiellen Hierarchie werden also mittels logischer
Ausdrückbarkeit beschrieben
Frage nach Echtheit der Inklusionen in PH: liefern zusätzliche Quantorenalternierungen zusätzliche Ausdrucksstärke?
16
Charakterisierung PH
Lemma
Für L ⇤ ⇤⇥ gilt L ⇧ ⇤pk gdw. es gibt Polynom p und Relation R ⇤ ⇤⇥
so dass
⇥
• (w, b) ⇧ R impliziert |b| ⌅ p(|w|)
• R ⇧ ⇥pk
1
(wobei ⇥p0 := P)
• L = {w | ⌃b : (w, b) ⇧ R}
Idee:
• Induktion über k
• Der Fall k = 1 folgt direkt aus Definition NP
• In ”⇥” ist der Beweis b eine Berechnung der NTM zusammen mit Beweisen für die ”ja”-Antworten des Orakels (induktiv)
17
Charakterisierung PH
Korollar
Für L ⇤ ⇤⇥ gilt L ⇧ ⇥pk gdw. es gibt Polynom p und Relation R ⇤ ⇤⇥
so dass
⇥
• (w, b) ⇧ R impliziert |b| ⌅ p(|w|)
• R ⇧ ⇤pk
1
(wobei ⇤p0 := P)
• L = {w | ⌃b ⇧
⇥
mit |b| ⌅ p(|w|) : (w, b) ⇧ R}
Beweis: Für L ⇤ ⇥pk gibt es R wie in vorigem Lemma, verwende für L:
R := {(w, b) ⇤ ⇥
| (w, b) ⇤
/ R und |b| ⇥ p(|w|)}
Aus Lemma + Korollar folgt nun das ursprüngliche Theorem:
Ersetze wiederholt ⇥pi und pi durch ihre Beweissysteme
18
Kapitel 7
Härte und Vollständigkeit in der polynomiellen Hierarchie
19
Vollständigkeit
Um Probleme korrekt in die polynomielle Hierarchie "einzuordnen",
brauchen wir Vollständigkeitsbegriff
Definition
Für k
1 ist Problem L
• ⌃pk -hart wenn L0 p L für alle L0 2 ⌃pk ;
• ⌃pk -vollständig wenn L sowohl ⌃pk -hart als auch in ⌃pk .
Für ⇧pk ,
p
k
und PH analog (außer für
p
1
= P)
Aber PH hat wahrscheinlich keine vollständigen Probleme:
Lemma
Wenn für PH vollständige Probleme existieren, kollabiert die Hierarchie
20
Vollständigkeit
QBF liefert uniforme Familie von „typischen“ vollständigen Problemen
Für V = v1 , . . . , vn schreiben wir ⇥V als Abkürzung für ⇥v1 · · · ⇥vn
⇥V als Abkürzung für ⇥v1 · · · ⇥vn
Definition k-QBF
QBF Q1 V1 · · · Qn Vn ' heißt k-QBF, wenn
• n=k
• Q1 = 9, Q2 = 8, Q3 = 9 etc. (Quantoren alternieren)
QBFk ist die Menge aller gültigen k-QBFs.
Beispiel für 3-QBF: ⇥v1 ⇥v2 v3 ⇥v4 ⇥v5 .
21
Vollständigkeit
Theorem
Für alle k
1 ist QBFk
p
k -vollständig.
Idee:
• “in ⌃pk ”: benutze logische Charakterisierung
• Härte: benutze logische Charakterisierung und Übersetzung
von TM in AL-Formel analog zum Beweis von Cook’s Theorem
Beginnt man die Quantorenalternierung mit “ ”, so ist k-QBF
p
k -vollständig.
22
Vollständigkeit
In der Logik gibt es verschiedene natürliche Probleme, die vollständig für Klassen der polynomiellen Hierarchie sind.
Definition MINSAT
Für zwei WZen und
schreiben wir
⇥
gdw.
(v) = 1 impliziert (v) = 1 für alle Variablen V
ist minimales Modell von AL-Formel ⇥ wenn
•
erfüllt ⇥
• für alle
, die ⇥ erfüllen, gilt
⇥
MINSAT ist die Menge aller Tripel (⇥, v) mit ⇥ AL-Formel und v Variable
so daß (v) = 0 in allen minimalen Modellen von ⇥.
Theorem
MINSAT ist
p
2 -vollständig.
23
Vollständigkeit
Weiteres natürliches vollständiges Problem z.B.:
Äquivalenzproblem für kontextfreie Grammatiken über
1-elementigen (Terminal-)Alphabeten ist p2 -vollständig.
Es wird vermutet, dass MC (Minimial Circuit) ebenfalls p2 -vollständig
ist, die Härte konnte aber bisher nicht bewiesen werden!
Für Klassen weit oben in der polynomiellen Hierarchie scheint es
nur sehr wenig „natürliche“ vollständige Probleme zu geben
24
Kapitel 7
P versus NP und das Theorem von Baker, Gill und Solovay
25
Baker, Gill und Solovay (BGS)
Warum ist P ≠ NP so schwer zu zeigen?
Theorem von BGS bietet eine Erklärung dafür:
Theorem (Baker, Gill, Solovay 1975)
Es gibt Orakel A und B, so dass PA = NPA und PB 6= NPB .
Das heißt: ein Beweis für P ≠ NP darf nicht relativierbar sein
Das schließt die meisten (elementaren) Beweistechniken aus
26
BGS: der Fall PA = NPA
Der einfachere Teil:
Lemma
Es gibt ein Orakel A, so dass PA = NPA .
Idee:
• Wählen als A ein beliebiges PS PACE-vollständiges Problem
(1)
A
A
• Zeigen: PS PACE ✓ P ✓ NP
(2)
✓ PS PACE
(1) Für L 2 PS PACE, berechne Reduktionsfunktion für L p A
und befrage Orakel
(2) Für L 2 NPA , integriere Orakelberechnung in Basis-ONTM
NPS PACE-Maschine
27
BGS: der Fall PB ≠ NPB
Der anspruchsvollere Teil:
Lemma
Es gibt ein Orakel B, so dass PB 6= NPB .
Idee:
• Eingabealphabet für alle TM sei {0, 1} (o. B. d. A.)
• Ziel: konstruieren Orakel B und Problem LB 2 NPB \ PB
• Wenn B konstruiert ist, können wir LB setzen als
LB = {1n | 9w 2 B : |w| = n}
1. Leicht zu sehen: LB 2 NPB , unabhängig von B
2. Müssen noch B ✓ {0, 1}⇤ so konstruieren, dass LB 2
/ PB ,
d. h.: für jede Polyzeit-ODTM M ? muss gelten: L(M B ) 6= LB (⇤)
28
BGS
BGS’ Ansatz hat zu zahlreichen ähnlichen Resultaten geführt, z.B.:
• Es gibt Orakel A und B, so dass NPA = co-NPA und NPB 6= co-NPB .
• Es gibt ein Orakel A, so dass NPA = co-NPA und PA 6= NPA .
• Es gibt Orakel A und B, so dass
– für NPA \ co-NPA vollständige Probleme existieren und
– für NPB \ co-NPB nicht
Probabilistische Analyse liefert zudem:
Für fast alle Orakel A gilt PA 6= NPA
29
Über BGS hinaus
„Moderner Nachfahre“ von BGS für Schaltkreistheorie:
Theorem von Razborov und Rudich (1997) schließt natürliche Beweise
für super-polynomielle Schaltkreiskomplexität aus
(EATCS-Gödelpreis 2007)
Es gibt neue Ansätze zum Beweis von P ≠ NP,
die weder von BGS noch RR ausgeschlossen werden:
z.B. über algebraische Geometrie (Mulmuley 2012)
30
Abschließende Bemerkung
Wie viele Komplexitätsklassen gibt es eigentlich?
31
Hierarchie der Komplexitätsklassen (Ausschnitt)
ALL
AH
RE
R
PR
ELEMENTARY
NEEE
P-Sel
NEEXP
EEE
EEXP
EESPACE
MIP_{EXP}
EXPSPACE
IP_{EXP}
SEH
EXP^{NP}
PEXP
NEE
AM_{EXP}
NEXP/poly
MA_{EXP}
EXP/poly
NEXP
BPEE
BPEXP
EXP
EXPH
NEXP^{NP}
EE
+EXP
QRG
ESPACE
RG
Almost-PSPACE
QPSPACE
PSPACE
Coh
PL_{infty}
CH
MP^{#P}
AvgE
P^{PP}
PP/poly
EH
P^{#P[1]}
BP.PP
MP
PH
Sigma_3P
QMIP
BQP/qpoly
BQP/mpoly
NE/poly
BQP/poly
(NP-cap-coNP)/poly
XOR-MIP*[2,1]
QSZK
BPP/rlog
NP/log
BPP/log
NE
QMA
NISZK
MA
MA_E
WAPP
NP
RP
Q
RNC
NC
QCFL
AL
+L/poly
NL/poly
L/poly
L^{DET}
SAC^1
PL
C_=L
NL
1NAuxPDA^p
SPL
CFL
AC^1
CSL
BPL
DCFL
FOLL
L
NC^1
QACC^0
TALLY
TC^0
QAC^0
MAC^0
AC^0/poly
QNC^0
polyL
R_HL
QNC^1
AC^0
SAC^0
+SAC^0
NC^0
PARITY
PBP
REG
ACC^0
AC^0[2]
QNC_f^0
UAP
UP
LogFew
TC^0/poly
PL_1
FewP
NT
EP
SC
RL
UL
SPARSE
QPLIN
Mod_3P
NT*
NLINSPACE
NLIN
LIN
FewUL
PT_1
P^{FewP}
Few
+P
SPP
GCSL
LFew
FewL
betaP
beta_2P
Mod_5P
NC^2
+SAC^1
+L
EQP
ModP
LWPP
RP^{PromiseUP}
QP
HalfP
P
BH
US
SUBEXP
ZPP
WPP
BH_2
ZQP
ZBQP
Check
C_=P
UE
ZPE
RQP
RBQP
QNC
P-Close
P^{NP[log]}
E
compNP
SF_3
SF_2
APP
AWPP
BPQP
BPP
YP
BPP_{path}
BPE
RPE
TreeBQP
PP
A_0PP
P^{NP[log^2]}
AmpP-BQP
FH
AvgP
QS_2P
P^{QMA}
Delta_2P
SBP
PZK
P/log
frIP
ZPP^{NP}
S_2P
QCMA
N.BPP
AVBPP
compIP
AM
SZK
YPP
BPP^{NP}
RP^{NP}
NISZK_h
BQP
HeurBPP
Sigma_2P
AM[polylog]
CZK
NIQSZK
Delta_3P
RG[1]
IP
QAM
N.NISZK
YQP
MIP
QIP[2]
DQP
BPP/mlog
NP/one
QMA(2)
NP/poly
BQP/log
SQG
QIP
BQP/mlog
BPP//log
Nearly-P
QMIP_{ne}
BQP/qlog
P/poly
IC[log,poly]
QMIP_{le}
MIP*
SF_4
AmpMP
(k>=5)-PBP
MAJORITY
4-PBP
3-PBP
2-PBP
NONE
32
Mehr Komplexitätsklassen
Abgesehen von den angegebenen Büchern:
https://complexityzoo.uwaterloo.ca/Complexity_Zoo
http://www.math.ucdavis.edu/~greg/zoology/
33