View
107
Download
0
Category
Preview:
Citation preview
Black Box Algorithmen
Hartmut KlauckUniversität FrankfurtSS 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
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
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
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
Beispiel 2
Graphzusammenhang C1(connect)=n-1
C0(connect)=n2/4
Beispiel 3
Parität: Parity(x1,…,xn)=1 gdw. Anzahl xi=1 ist ungerade
C0(Parity)=C1(Parity)=n
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
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
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)
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
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
Beispiel
C0(f),C1(f)=n1/2
C0: fix. OR C1: fix. 1 per AND
Aber: D(f)=n Also Theorem optimal
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
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
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
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)
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)
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
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
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
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)
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?
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
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
Recommended