Komplexitätstheorie

Kapitel 7: Orakel

Einleitung

2

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

Kapitel 7

3

Die Polynomielle Hierarchie (PH)

PH

4

(N)LogSpace, NC, AC, etc: reiche Struktur innerhalb von P

Die polynomielle Hierarchie liefert Struktur zwischen P und PSpace

Definition Minimal Circuit (MC)

Wichtiges Problem für Schaltkreisentwurf:

Schaltkreis C ist minimal wenn |C �| � |C| fur alle C �, die aquivalent zu C

sind, also gleiche Anzahl n von Eingabebits und

C(w) = C �(w) fur alle w ⇥ {0, 1}n

MC ist Menge aller minimalen Schaltkreise.

Was ist die ”richtige” Komplexitatsklasse (Vollstandigkeit!) fur diesesProblem?

PH

5

Offensichtliches “Teilproblem” ist CEQ := {(C, C �) | C aquivalent zu C �}

Lemma

CEQ ist co-NP-vollstandig.

Betrachte wieder MC:

• Ist in NP wenn wir einen CEQ-Algorithmus als Unterprozedurohne Zeitverbrauch verwenden

• Wir konnen beide Algorithmen nicht zu einem NP-Algorithmusvereinigen, weil der NP-Algorithmus einen co-NP-Algorithmus aufruft(⇤⇥-Charakteristik)

Derartige Probleme sind offensichtlich in PSpace. Man kann derenKomplexitat aber noch exakter bestimmen

Orakel

6

Orakel: Unterprogramm, dessen Zeitverbrauch ausgeblendet wird,

Definition Orakel-TM

Eine Orakel-TM (OTM) MO ist eine (deterministische oder nicht-deter-ministische) TM M ausgestattet mit einem Orakel O ⇥ �⇥. OTM hat

• ein zusatzliches Orakelband

• drei spezielle Zustande q?, q+, q�.

Fur q+ und q� sind normale Transitionen definiert. Der Folgezustandvon q? ist q+ wenn das momentane Wort auf dem Orakelband in O istund q� sonst. Kopfposition und Bandinhalte bleiben dabei unverandert.

dargestellt als formale Sprache

Also schon gesehen: MC wird von Polyzeit-beschrankter ONTM akzeptiertwenn O=CEQ

Orakel

7

Orakel-TMs können auch verwendet werden, um komplexitäts-theoretische 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)

Orakel-TM ist ebensowenig realistisches Berechnungsmodell wie nicht-deterministische TMs

Dennoch können mittels Orakel-TMs natürliche Komplexitätsklassendefiniert werden (natürlich = erfassen viele natürliche Probleme)

Orakel

8

Definition Orakel-Komplexitätsklassen

Sei O ⇥ �� ein Orakel. Dann:

• PO := {L | L wird von ODTM MO in poly-Zeit entschieden }

• NPO := {L | L wird von ONTM MO in poly-Zeit entschieden }

Sei C Komplexitatsklasse. Dann:

PC :=�

O⇥CPO NPC :=

�

O⇥CNPO

Schon gezeigt: MC � NPCEQ, also in MC � NPco-NP

Leicht zu sehen: NPco-NP = NPNP

PH

9

Einige Beispiele:

• PP = P, NPP = NP;

(Integriere Orakel in OTM)

• NPNP = NP ist hingegen nicht klar, denn co-NP ✓ Pco-NP = PNP ✓ NPNP

• PNP = PSAT und ebenso fur jedes andere NP-vollstandige Problem

(Genugt zu zeigen: PO ✓ PSAT mit O 2 NPintegriere dazu Reduktion O p SAT in OTM)

co-NPC verwenden wir fur NPC

PH: Definition

10

Die polynomielle Hierarchie entsteht nun durch iteriertes Orakel-anwenden

Definition Polynomielle Hierarchie

• �p1 = P, ⌃p

1 = NP, ⇧p1 = co-NP,

• F¨ur k � 1 sei

– �pk+1 = P⌃p

k

– ⌃pk+1 = NP

⌃pk

– ⇧pk+1 = co-⌃p

k+1

PH: Bild und einfache Eigenschaften

11

�p1 = P

�p1 = NP �p

1 = co-NP

� �

� �

� �

� �

...

Echtheit der Inklusionen istunbekannt.

Lemma

Fur alle k ⇥ 1 gilt: �pk � ⇤p

k � �pk+1 und �p

k � ⇥pk � �p

k+1

�p2 = NPNP �p

2 = co-NPNP

�p2 = PNP

�p3 = PNPNP

Die Klasse PH

12

Definition Polynomielle Hierarchie

Theorem

PH =�

k�1 �pk

Es gibt auch eine Klasse für die gesamte polynomielle Hierarchie:

Die polynomielle Hierarchie liegt zwischen P und PSpace:

PH � PSPACE

Kollaps der PH

13

Lemma

Wenn �pk = �p

k+1, dann PH = �pk.

Theorem

Wenn PH = PSPACE, dann kollabiert PH.

und P �= NP schwachste aller dieser Annahmen

Anders formuliert: PH kollabiert am ehesten weit oben!

Viele Resultate in der Komplexitätstheorie beziehen sich auf die Echtheit der Inklusionen in der polynomiellen Hierarchie

Also: �pk�1 �= �p

k schwachere Annahme als �pk �= �p

k+1

Die polynomielle Hierarchie kollabiert wenn PH = �pk fur ein k � 1

Eine nützliche Eigenschaft

14

Lemma

Eine Aussage über eingeschränkte Interaktion mit dem Orakel

Sei MO eine Polyzeit-ONTM mit Orakel O 2 ⌃pk mit q+ = qacc

(d. h.: MO akzeptiert, sobald eine Orakelfrage positiv beantwortet wird).

Dann gilt: L(MO) 2 ⌃pk.

Lemma

Sei MO eine Polyzeit-ONTM mit Orakel O 2 ⇧pk mit q� = qrej.

Dann gilt: L(MO) 2 ⇧pk.

Idee:• rate Orakelantworten im Voraus

• integriere O-Berechnung – verwirf bei abweichenden Antworten sofort

Analoge Aussage per Komplementierung:

Kapitel 7

15

Logische Charakterisierung der Polynomiellen Hierarchie

Charakterisierung PH

16

Folgende Charakterisierung generalisiert Definition von NP

Theorem

Frage nach Echtheit der Inklusionen in PH: liefern zusätzliche Quantoren-alternierungen zusätzliche Ausdrucksstärke?

Die Klassen der polynomiellen Hierarchie werden also mittels logischerAusdrückbarkeit beschrieben

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}.

L 2 ⌃pk gdw. es Polynom q und L0 2 P gibt, so dass

L = {w | 9u12A . 8u22A . 9u32A . . . Quk2A : (w, u1, . . . , uk) 2 L0},

wobei A = {0, 1}q(|w|)und Q der sich durch Alternierung ergebende Quantor.

Charakterisierung PH

17

LemmaFur L ⇤ ⇤⇥ gilt L ⇧ ⇤p

k gdw. es gibt Polynom p und Relation R ⇤ ⇤⇥ � �⇥

so dass

• (w, b) ⇧ R impliziert |b| ⌅ p(|w|)

• R ⇧ ⇥pk�1 (wobei ⇥p

0 := P)

• L = {w | ⌃b : (w, b) ⇧ R}

Idee:

• Induktion uber k

• Der Fall k = 1 folgt direkt aus Definition NP

• In ”⇥” ist der Beweis b eine Berechnung der NTM zusammen mit Be-weisen fur die ”ja”-Antworten des Orakels (induktiv)

Charakterisierung PH

18

Korollar

Beweis: Fur L ⇤ ⇥pk gibt es R wie in vorigem Lemma, verwende fur L:

�R := {(w, b) ⇤ ⇥� � �� | (w, b) /⇤ R und |b| ⇥ p(|w|)}

Aus Lemma + Korollar folgt nun das ursprungliche Theorem:Ersetze wiederholt ⇥p

i und �pi durch ihre Beweissysteme

Fur 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 ⇤p

0 := P)

• L = {w | ⌃b ⇧ �⇥ mit |b| ⌅ p(|w|) : (w, b) ⇧ R}

Kapitel 7

19

Härte und Vollständigkeit in der polynomiellen Hierarchie

Vollständigkeit

20

Definition

LemmaWenn für PH vollständige Probleme existieren, kollabiert die Hierarchie

Aber PH hat wahrscheinlich keine vollständigen Probleme:

Um Probleme korrekt in die polynomielle Hierarchie "einzuordnen",brauchen wir Vollständigkeitsbegriff

Fur k � 1 ist Problem L

• ⌃pk-hart wenn L0 p L fur alle L0 2 ⌃p

k;

• ⌃pk-vollst

¨

andig wenn L sowohl ⌃pk-hart als auch in ⌃p

k.

Fur ⇧pk, �p

k und PH analog (außer fur �p1 = P)

Vollständigkeit

21

Definition k-QBF

QBF liefert uniforme Familie von „typischen“ vollständigen Problemen

Fur V = v1, . . . , vn schreiben wir ⇥V als Abkurzung fur ⇥v1 · · · ⇥vn

⇥V als Abkurzung fur ⇥v1 · · · ⇥vn

Beispiel fur 3-QBF: ⇥v1⇥v2�v3⇥v4⇥v5.�

QBF Q1V1 · · ·QnVn' heißt k-QBF, wenn

• n = k

• Q1 = 9, Q2 = 8, Q3 = 9 etc. (Quantoren alternieren)

QBFk ist die Menge aller g¨ultigen k-QBFs.

Vollständigkeit

22

TheoremFur alle k � 1 ist QBFk �p

k-vollstandig.

Beginnt man die Quantorenalternierung mit “�”, so ist k-QBF �pk-vollstandig.

Idee:

• “in ⌃pk”: benutze logische Charakterisierung

• Harte: benutze logische Charakterisierung und Ubersetzungvon TM in AL-Formel analog zum Beweis von Cook’s Theorem

Vollständigkeit

23

Definition MINSAT

In der Logik gibt es verschiedene natürliche Probleme, die voll-ständig für Klassen der polynomiellen Hierarchie sind.

Fur zwei WZen � und �� schreiben wir � ⇥ �� gdw.

��(v) = 1 impliziert �(v) = 1 fur alle Variablen V

� ist minimales Modell von AL-Formel ⇥ wenn

• � erfullt ⇥

• fur alle ��, die ⇥ erfullen, gilt � ⇥ ��

MINSAT ist die Menge aller Tripel (⇥, v) mit ⇥ AL-Formel und v Variableso daß �(v) = 0 in allen minimalen Modellen von ⇥.

TheoremMINSAT ist �p

2-vollstandig.

Vollständigkeit

24

Für Klassen weit oben in der polynomiellen Hierarchie scheint esnur sehr wenig „natürliche“ vollständige Probleme zu geben

Aquivalenzproblem fur kontextfreie Grammatiken uber1-elementigen (Terminal-)Alphabeten ist �p

2-vollstandig.

Weiteres natürliches vollständiges Problem z.B.:

Es wird vermutet, dass MC (Minimial Circuit) ebenfalls �p2-vollstandig

ist, die Harte konnte aber bisher nicht bewiesen werden!

Kapitel 7

25

P versus NP und das Theorem von Baker, Gill und Solovay

Baker, Gill und Solovay (BGS)

26

Warum ist P ≠ NP so schwer zu zeigen?

Theorem von BGS bietet eine Erklärung dafür:

Das heißt: ein Beweis für P ≠ NP darf nicht relativierbar sein

Das schließt die meisten (elementaren) Beweistechniken aus

Theorem (Baker, Gill, Solovay 1975)

Es gibt Orakel A und B, so dass PA = NPA und PB 6= NPB .

BGS: der Fall PA = NPA

27

Lemma

Idee:

• Wahlen als A ein beliebiges PSPACE-vollstandiges Problem

• Zeigen: PSPACE(1)✓ PA ✓ NPA

(2)✓ PSPACE

(1) Fur L 2 PSPACE, berechne Reduktionsfunktion fur L p A

und befrage Orakel

(2) Fur L 2 NPA, integriere Orakelberechnung in Basis-ONTM NPSPACE-Maschine

Der einfachere Teil:

Es gibt ein Orakel A, so dass PA = NPA.

BGS: der Fall PB ≠ NPB

28

Lemma

Der anspruchsvollere Teil:

Es gibt ein Orakel B, so dass PB 6= NPB .

Idee:

• Eingabealphabet fur alle TM sei {0, 1} (o. B. d. A.)

• Ziel: konstruieren Orakel B und Problem LB 2 NPB \ PB

• Wenn B konstruiert ist, konnen wir LB setzen als

LB = {1n | 9w 2 B : |w| = n}

1. Leicht zu sehen: LB 2 NPB , unabhangig von B

2. Mussen noch B ✓ {0, 1}⇤ so konstruieren, dass LB /2 PB ,d. h.: fur jede Polyzeit-ODTM M? muss gelten: L(MB) 6= LB (⇤)

BGS

29

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

– fur NPA \ co-NPA vollstandige Probleme existieren und

– fur NPB \ co-NPB nicht

Probabilistische Analyse liefert zudem:

Fur fast alle Orakel A gilt PA 6= NPA

Über BGS hinaus

30

„Moderner Nachfahre“ von BGS für Schaltkreistheorie:

Theorem von Razborov und Rudich (1997) schließt natürliche Beweisefü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)

Abschließende Bemerkung

31

Wie viele Komplexitätsklassen gibt es eigentlich?

Hierarchie der Komplexitätsklassen (Ausschnitt)

32

(NP-cap-coNP)/poly

NP/poly

PP/poly

NE/poly

(k>=5)-PBP

NC^1 PBP

LQNC^1

CSL

+EXP

EXPSPACE

EESPACEEEXP

+L

+L/poly +SAC^1

AL

P/poly

NC^2

P

BQP/poly

+P

ModP

SF_2

AmpMP

SF_3

+SAC^0

AC^0[2]

QNC_f^0

ACC^0

QACC^0

NC

1NAuxPDA^p

SAC^1

AC^1

2-PBP

3-PBP

4-PBP

TC^0

TC^0/poly

AC^0

AC^0/poly

FOLL

MAC^0QAC^0

L/poly

AH

ALL

AvgP

HalfP

NT

P-Close

P-Sel

P/log

UPbeta_2P

compNP

AM

AM[polylog]

BPP^{NP}

QAM

Sigma_2P

ZPP^{NP}

IP

Delta_3PSQG

BP.PP

QIP[2] RP^{NP}

PSPACE

MIPMIP* QIP

AM_{EXP}

IP_{EXP}

NEXP^{NP}

MIP_{EXP}

EXPH

APP

PP

P^{#P[1]}

AVBPP

HeurBPP

EXP

AWPP

A_0PP

Almost-PSPACE

BPEXP

BPEEMA_{EXP}

MP

AmpP-BQP

BQP

Sigma_3P

BQP/log

DQP

NIQSZK QCMAYQP

PH

AvgE

EE

NEE

ENearly-P

UE

ZPE

BH

P^{NP[log]}

BPP_{path}

P^{NP[log^2]}

BH_2

CH

EXP/poly

BPE

MA_E

EH

EEE

PEXP

BPL

PL

SC

NL/poly

L^{DET}

polyL

BPP

BPP/log

BPQP

Check

FH

N.BPP

NISZK

PZK

TreeBQP

WAPP

XOR-MIP*[2,1]

BPP/mlog

QPSPACE

frIP

MA

N.NISZK

NISZK_h

SZK

SBP

QMIP_{le}

BPP//log

BPP/rlog

BQP/mlog

BQP/qlog

QRG ESPACE

QSZK

QMA

BQP/qpoly

BQP/mpoly

CFL

GCSL

NLIN

QCFL

Q

NLINSPACE

RG

CZK

C_=L

C_=P

Coh

DCFL

LIN

NEXP

Delta_2P

P^{QMA}S_2P

P^{PP}

QS_2P

RG[1]

NE

RPE

NEEXP

NEEE

ELEMENTARY

PR

R

EP

Mod_3PMod_5P

NP

NP/one RP^{PromiseUP}US

EQP

LWPP

ZQP

WPP

RQP

NEXP/poly

EXP^{NP}

SEH

Few

P^{FewP}

SPP

FewL

LFew

NL SPL

FewP

FewUL

LogFew

RP

ZPP

RBQPYP

ZBQP

IC[log,poly]

QMIP_{ne}QMIP

R_HLUL

RL

MAJORITY

PT_1

PL_{infty}

MP^{#P}

SF_4

RNC

QNC

QP

NC^0

PL_1

QNC^0 SAC^0

NONE

PARITY

TALLY

REG

SPARSE

NP/log

NT*

UAPQPLINbetaP

compIP

RE

QMA(2)

SUBEXP

YPP

Mehr Komplexitätsklassen

33

http://www.math.ucdavis.edu/~greg/zoology/https://complexityzoo.uwaterloo.ca/Complexity_Zoo

Abgesehen von den angegebenen Büchern: