25
Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5.

Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Embed Size (px)

Citation preview

Page 1: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Black Box Algorithmen

Hartmut KlauckUniversität FrankfurtSS 05

18.5.

Page 2: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Diese Vorlesung

Techniken für untere Schranken Vergleich Nichtdeterminismus und

Determinismus für Entscheidungsbäume

Sensitivität, Blocksensitivität, Zertifikate und Tiefe

Page 3: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Zertifikate

Definition 9.1 Ein Term der Form

c=(xi(1)=b1 Æ…Æ xi(k)=bi(k)) heisse ein a-Zertifikat für eine Boolesche Funktion f, wenn für alle Eingaben x2 {0,1}n die mit dem Term übereinstimmen, f(x)=a gilt

Eingabe x hat Zertifikat c, wenn c auf x wahr k sei die Länge des Zertifikates f habe Zertifikatskomplexität k, wenn es für

alle Eingaben ein Zertifikat der Länge k gibt, und für kleinere k‘ dies nicht gilt

Dann sei C(f)=k

Page 4: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Zertifikate

Definition 9.2f habe a-Zertifikatskomplexität k, wenn

es für alle Eingaben mit f(x)=a ein Zertifikat der Länge k gibt, und für kleinere k‘ dies nicht gilt

Dann sei Ca(f)=k

Page 5: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Beispiel

C1(OR)=1,

Verwende Zertifikate xi=1

C0(OR)=n Wenn nicht alle Bits auf 1 gesetzt

sind, ist OR(x)=1 möglich C(OR)=n

Page 6: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Beispiel 2

Graphzusammenhang C1(connect)=n-1

C0(connect)=n2/4

Page 7: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Beispiel 3

Parität: Parity(x1,…,xn)=1 gdw. Anzahl xi=1 ist ungerade

C0(Parity)=C1(Parity)=n

Page 8: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

C(f) und D(f)

Theorem 9.3 D(f)¸ C(f)

Beweis: Betrachte Blatt im Entscheidungsbaum Abfrageergebnisse auf dem Pfad zum Blatt sind

Zertifikat Wenn Tiefe d < C(f) dann gibt es für eine Eingabe x

kein Zertifikat der Länge d Eingabe x landet an Blatt, bei dem sowohl zu

verwerfende als auch zu akzeptierende Eingaben landen

Page 9: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Nichtdeterminismus

Definition 9.4Ein nichtdeterministischer

Entscheidungsbaum hat zusätzliche Knoten, an denen verzweigt wird, ohne eine Variable zu lesen

Eingaben werden akzeptiert, wenn es einen akzeptierenden Pfad gibt

Tiefe sei maximale Anzahl der gelesenen Variablen auf einem Pfad

Page 10: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Nichtdeterminismus

Beobachtung: Die minimale Tiefe eines nichtdeterministischen

Entscheidungsbaumes für f ist genau C1(f) Beweis:

Tiefe ¸ C1(f):• Genau wie bei D(f), mit Einschränkung auf 1-Eingaben

Tiefe · C1(f):• Fixiere Menge von Zertifikaten für alle 1-Eingaben• Baum ist Verzweigung an der Wurzel, gefolgt von

Zertifikaten Beobachtung 2:

Der nichtdeterministische Baum entspricht einer DNF, mit Monomlänge C1(f)

Page 11: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Nichtdeterminismus

C1(OR)=1, aber D(OR)¸ C0(OR)¸ n Daher bringt Nichtdeterminismus eine

unbeschränkte Senkung der Komplexität

Im Entscheidungsbaummodell gilt„P NP“ und „NP co-NP“

P, NP etc: Boolesche Funktionen, die mit polylogarithmischer Tiefe berechenbar sind

Page 12: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

C(f) vs. D(f)

Theorem 9.5 D(f)· C0(f) C1(f)

Kommentar: „P=NPÅ co-NP“ im Entscheidungsbaummodell

D(f) gross: wenn C0(f) klein, dann ist C1(f) gross

Beispiel: AND(OR(…),OR(…),…,OR(…)) Formel Tiefe 2 mit Grad n1/2

Page 13: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Beispiel

C0(f),C1(f)=n1/2

C0: fix. OR C1: fix. 1 per AND

Aber: D(f)=n Also Theorem optimal

Page 14: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Beweis 9.5

Beobachtung: Jedes Paar von 1-Zertifikat und 0-Zertifikat

hat gemeinsame Variable Denn sonst gibt es eine Eingabe, die mit

beiden konsistent! Algorithmus:

Exponiere 1-Zertifikat Kürze alle 0-Zertifikate Bis nicht mehr möglich

Page 15: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Der Algorithmus

C1(f)=k, C0(f)=l K:Menge von 1-Zertifikaten der Länge k, die 1-

Eingaben überdeckt L:Menge von 0-Eingaben …

Wähle c aus K, Frage alle Variablen in c c erfüllt: Akzeptiere Sonst: Entferne c aus K Für alle d aus L: wenn d noch konsistent mit

gelesenen Var., dann entferne aus d bekannte Variablen, sonst entferne d

Wenn L leer ist: akzeptiere Wenn L nur noch triviale Zertifikate enthält:

Verwerfe Wenn K leer ist: verwerfe

Page 16: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Analyse

Korrektheit: Für alle Eingaben x gibt es ein 0-Zert. oder

ein 1-Zert. f(x)=0, dann wird 0-Zert. nie entfernt, also

wird verworfen f(x)=1, mit 1-Zert. c: Entweder

c wird gefragt, dann wird akz. Oder: Es werden andere c‘ aus K gefragt, bis

L leer Es wird akzeptiert

Page 17: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Laufzeit

Wenn c aus K gefragt wird, werden alle d aus L entweder gestrichen, oder um 1 Variable gekürzt

Kosten des Fragens von c: k Anzahl der Runden, bis L leer: höchstens l In allen anderen Fällen wird vorher

entschieden Gesamt: D(f)· kl=C0(f)C1(f)

Page 18: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Zusammengefasst

C(f)· D(f)· C2(f) C1(f),C0(f)· D(f)· C0(f)C1(f)

Nichtdeterminismus entspricht C1

Untere Schranken oft einfacher für C(f) Manchmal sind untere Schranken via C(f)

quadratisch schlechter als D(f)

Page 19: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Sensitivität

f sei Boolesche Funktion Eine Eingabe x2{0,1}n ist sensitiv für

eine Position i, wenn f(x(i)) f(x), wobei x(i) wie x mit i-tem Bit geflippt

Sensitivität s(f,x): Anzahl der sensitiven Positionen auf x

Sensitivität s(f): Maximum über alle x

Page 20: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Untere Schranke

Theorem 9.6 D(f)¸ s(f)

Beweis: Übung

Beispiel OR: Eingabe 0n ist sensitiv auf n Positionen, Eingaben mit einer 1 sind sensitiv auf 1 Position, alle anderen auf 0

D(OR)¸ s(OR)=n

Page 21: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Beispiel

Connectivity:Graph sei spannender Baum, dann ist

Sensitivität n-1Graph bestehe aus zwei spannenden

Bäumen auf n/2 Kanten dann gibt es n2/4 Kanten die Zusammenhang herstellen

s(Connect)=(n2) also

Page 22: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Block-Sensitivität

Es ist unbekannt, ob D(f)=poly(S(f)) Neues Konzept: erlaube, Blöcke von

Variablen zu flippen Definition 9.7

bs(f,x) sei Maximum der Werte k über alle Wahlen von k disjunkten Mengen B1,...,Bk von Variablen, so dass für jedes i=1,...,k gilt: f(x) f(x‘), wobei x‘ sich durch flippen aller Bits in Bi ergibt

bs(f)=maxx bs(f,x)

Page 23: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Relationen zwischen den Massen Klar: s(f)· bs(f) Beobachtung: bs(f)· C(f)

Denn: Zertifikat muss eine Variable aus jedem Block testen

Also s(f)· bs(f)· C(f)· D(f)

Weiterhin bekannt: s(f)=(log n) für alle nichttrivialen Funktionen, die von n Variablen anhängen, und D(f)· n

Gibt es einen Unterschied zwischen s und D?

Page 24: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Unterschied s(f) und bs(f)

Theorem 9.8 Es gibt eine Boolesche Funktion f mit

s(f)=n1/2 und bs(f)=n/2 Beweis:

f: n1/2 Blöcke von n1/2 Variablen f(x)=1, wenn es einen Block gibt mit 2

Einsen nacheinander und sonst Nullen bs(f)¸ n/2: 0n ist sensitive Eingabe s(f)· n1/2: Übung

Page 25: Black Box Algorithmen Hartmut Klauck Universität Frankfurt SS 05 18.5

Unterschied bs(f), D(f)

And OR Formel Tiefe 2 mit n Variablen, Grad n1/2

bs(f)· C(f) = n1/2

Aber D(f)=n