Graphen und Algorithmen II 001

Graphen und Algorithmen II Skript zur Vorlesung von Dr. Amin Coja-Oghlan Institut f¨ ur Informatik, Humboldt Universit¨ at Berlin Sommersemester 2004

Ulf Hermann eMail:

(185523) [email protected]

Genevi`eve Grunert eMail:

(171756) [email protected]

Alexander Hentschel eMail:

(176835) [email protected]

Inhaltsverzeichnis

Graphen und Algorithmen II

Inhaltsverzeichnis 1 Vorwort

3

2 Einf¨ uhrung und Wiederholung ¨ 2.1 Uberblick . . . . . . . . . . . . . . . . . . . . 2.2 P und N P . . . . . . . . . . . . . . . . . . . 2.3 Grundbegriffe der Wahrscheinlichkeitstheorie 2.4 Polynome u orpern . . . . . . ¨ber endlichen K¨

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5 . 5 . 7 . 10 . 12

3 Formulierung des P CP -Theorems 17 3.1 Schaltnetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Das P CP -Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 NP 4.1 4.2 4.3

⊂ P CP (n3 , 1) Arithmetisierung boolescher Formeln . . . . . . . . . . . . . . . . . . . . Linearit¨ atstest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N P ⊂ P CP (n3 , 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19 20 22 25

5 NP 5.1 5.2 5.3 5.4 5.5 5.6

⊂ P CP (log n, poly(log n)) probabilistisch pr¨ ufbare L¨ osungen . . . . . Testen von Polynomen niedrigen Grades . Codieren mittels Polynomen . . . . . . . . Der (erweiterte) LFKN-Test . . . . . . . . N P ⊂ P CP (log n, poly(log n)) . . . . . . (RE3SAT , E1 ) ∈ P CS(log n, poly(log n), 1)

27 27 28 30 31 35 37

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

6 Komposition der Verifizierer 40 6.1 Aufspalten der L¨ osungscodierung . . . . . . . . . . . . . . . . . . . . . . 41 6.2 Kompositionslemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 7 Nichtapproximierbarkeit von M AX(E)3SAT 7.1 Vorbemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Der Langcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Nichtapproximierbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . .

45 45 52 56

8 Korrektheitsbeweis des LowDegreeTests 8.1 Einige hilfreiche Aussagen aus der Algebra . . . 8.2 Der Satz von Arora und Safra . . . . . . . . . . 8.3 Folgerungen aus dem Satz von Arora und Safra 8.4 Der eigentliche Beweis . . . . . . . . . . . . . .

62 63 66 67 70

2

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

1 VORWORT

Graphen und Algorithmen II

1 Vorwort Gegenstand der Vorlesung ist das sogenannte PCP-Theorem (“probabilistically checkable proofs”) und die Theorie der Nichtapproximierbarkeit (genauer: “NP-hardness of approximation”). Das zentrale Ergebnis ist, daß es f¨ ur jede Konstant  > 0 NP-schwer ist, eine Approximationsg¨ ute von 87 +  f¨ ur das MAX E3SAT-Problem zu erzielen; dieses Problem ist eine Optimierungsversion des bekannten aussagenlogischen Erf¨ ullbarkeitsproblems SAT. Aus diesem fundamentalen Ergebnis lassen sich zahlreiche weitere Nichtapproximierbarkeitsresultate herleiten, z.B. f¨ ur Graphenprobleme wie Vertex Cover. Die Vorlesung ist folgendermaßen strukturiert. Kapitel 2 wiederholt Grundbegriffe aus der Theoretischen Informatik, der Algebra und der Wahrscheinlichkeitstheorie. In Kapitel 3 wird das PCP-Theorem formuliert, das in den Kapiteln 4–6 bewiesen wird. Im Einzelnen ist der Gegenstand von Kapitel 4 der relativ einfache Satz, daß NP⊂PCP(n3, 1), der mit Mitteln der Linearen Algebra zu beweisen ist. In Kapitel 5 wird die wesentliche schwierigere Beziehung NP⊂PCP(log n, poly(log n)) bewiesen. Daf¨ ur werden der sog. “Low Degree Test” sowie der “LFKN-Test” ben¨ otigt. Besonders der Korrektheitsbeweis des “Low Degree Tests”, der der Gegenstand von Kapitel 8 ist, ist technisch recht aufw¨ andig. Schließlich wird in Kapitel 6 das wichtige “Kompositionslemma” hergeleitet, aus dem mit Hilfe der Resultate der vorherigen beiden Kapitel die Aussage NP⊂PCP(log n, 1), also das “PCP-Theorem”, folgt. Das PCP-Theorem wiederum impliziert, daß es eine Zahl  > 0 gibt, so daß es NP-schwer ist, eine Approximationsg¨ ute von 1 −  f¨ ur das MAX E3SAT-Problem zu erzielen (das PCP-Theorem ist in der Tat ¨ aquivalent zu dieser Aussage). Dieses Nichtapproximierbarkeitsresultat f¨ ur MAX E3SAT wird im zweiten Teil der Vorlesung (Kapitel 7) verst¨ arkt, um das Hauptresultat zu erhalten, daß MAX E3SAT nicht effizient auf einen Faktor 87 + approximiert werden kann, sofern nicht P=NP. Um dieses Hauptresultat zu beweisen, wird das Paradigma des “¨ außeren” und “inneren” Verifizierers sowie Methoden der Fourieranalysis ben¨ otigt. Ferner ist das sog. “parallel repetition theorem” ein wichtiges Hilfsmittel. In diesem Text ist der Beweis des PCP-Theorems vollst¨ andig enthalten, insbesondere auch der Korrektheitsbeweis des “Low Degree Tests” sowie der Beweis des Kompoandig besitionslemmas. Auch das 78 + -Nichtapproximierbarkeitsresultat wird vollst¨ wiesen, mit Ausnahme des “parallel repetition theorems” (dessen Beweis eine eigene Vorlesung erfordert) sowie der ben¨ otigten S¨ atze der Fourieranalysis. Vorausgesetzt werden Grundkenntnisse in Mathematik und Theoretischer Informatik, wie sie im Grundstuidum Informatik vermittelt werden. Insbesondere werden elementare Kenntnisse der Komplexit¨ atstheorie wie etwa, daß das aussagenlogische Erf¨ ullbarkeitsproblem SAT NP-vollst¨ andig ist, ben¨ otigt (s. z.B. das einf¨ uhrende Buch von Papadimitriou [10]). F¨ ur einige Teile des Beweises des PCP-Theorems sind Algebrakenntnisse erforderlich, u.a. Lineare Algebra und Erweiterungsk¨ orper endlicher K¨ orper. Dieses Material kann z.B. Lang [9] entnommen werden. Schließlich verwendet Kapitel 7 Methoden der Fourieranalysis u ¨ber endlichen Gruppen, u.a. den Begriff der Fouriertransformierten, die Fourierinversionsformel sowie die Parsevalsche Identit¨ at. Die

3

1 VORWORT

Graphen und Algorithmen II

ben¨ otigten Begriffe und Resultate werden im Text selbst zitiert, f¨ ur Beweise kann etwa auf Rudin [12] verwiesen werden. Das Material der Kapitel 3–6 ist der Arbeit von Arora, Lund, Motwani, Sudan und Szegedy [1] entnommen. Kapitel 8 folgt [1] sowie Arora und Safra [2]. Die Darstellung dieses Materials folgt zum Teil Hougardy, Pr¨ omel und Steger [8] sowie Ausiello et al. [3, Kapitel 7]. Das 7. Kapitel gibt Teile von H˚ astads Arbeit [6] wieder und verwendet das “parallel repetition theorem” von Raz [11]. Der Zweck dieses Skriptes ist vor allem, die Teilnahme an der Vorlesung zu erleichtern vor dem Hintergrund, daß bisher keine geschlossene Darstellung des PCP-Theorems und der Theorie der Nichtapproximierbarkeit verf¨ ugbar ist. (Z.B. enthalten die Texte [3, 8] das Material des 7. Kapitels nicht und sind z.T. fehlerbehaftet.) Als Erg¨ anzung zur Vorlesung ist das Skript nur eingeschr¨ ankt zum Selbststudium geeignet. Ich m¨ ochte Frau Genevieve Grunert, Herrn Alexander Hentschel und Herrn Ulf Hermann f¨ ur die aufw¨ andige und gewissenhafte Anfertigung dieses Vorlesungsskriptes danken, das auf meiner Vorlesung “Graphen und Algorithmen 2” im Sommersemester 2004 beruht. Amin Coja-Oghlan

4

Graphen und Algorithmen II

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

2 Einf¨ uhrung und Wiederholung Vorlesung 15.04.04

¨ 2.1 Uberblick 2.1.1 Beispiele f¨ ur nicht approximierbare Probleme Graphenf¨ arbung: χ ist nicht auf n1−ε approximierbar. M AX3SAT : Dieses Problem ist das zentrale Thema der Vorlesung. – Gegeben sind n boolesche Variablen x1 , x2 , . . . , xn und eine Menge von Klauseln u ¨ber x1 , x2 , . . . , xn aus je 3 Literalen (z.B. xi ∨ xj ∨ xk ).

– Die Fragestellung: Gibt es eine Belegung der Variablen, so daß alle Klauseln erf¨ ullt sind? - Dieses Problem ist N P -vollst¨ andig. (Bezeichnung: 3SAT ) – Allerdings l¨ aßt sich auch eine Optimierungsversion formulieren: Finde eine Belegung der Variablen, so daß m¨ oglichst viele Klauseln erf¨ ullt sind. (Bezeichnung: M AX3SAT )

“Einfach” ist folgendes Problem: Finde eine Belegung, die 7/8 der Klauseln erf¨ ullt (zun¨ achst ohne Beweis). OP T sei nun die gr¨ oßte Zahl der Klauseln, die von irgendeiner Belegung erf¨ ullt wird. Ein “schwieriges” Problem ist nun, eine Belegung zu finden, die (7/8+ε)·OP T Klauseln erf¨ ullt. 2.1.2 Das P CP -Theorem (“probabilistically checkable proofs”) Das P CP -Theorem behauptet eine neue Charakterisierung der Klasse N P . Dazu wird eine Menge von Sprachklassen P CP konstruiert, in der N P als ein Element auftritt: N P = P CP (log n, 1). Auch der Begriff des Beweises wird dabei geeignet neu gefaßt. Ein Beweis f¨ ur Probleme in N P ist z.B.: eine erf¨ ullende Belegung einer 3SAT -Formel eine Belegung, die mehr als 7/8 der Klauseln einer M AX3SAT -Instanz erf¨ ullt eine 3-F¨ arbung eines Graphen Zun¨ achst wollen wir die beiden Klassen definieren. Die Klasse N P kennen wir schon. Zum besseren Vergleich wiederholen wir die Definition aber noch einmal. Angenommen es gibt einen “allm¨ achtigen” Beweiser, der einen Beweis von in der Eingabel¨ ange polynomieller L¨ ange f¨ ur die Eingabe (z.B. eine 3SAT -Formel) finden kann. Ein Problem liegt in N P, wenn es nun einen Pr¨ ufer gibt, der einen beliebigen solchen Beweis in polynomieller Zeit pr¨ ufen kann. Dazu betrachtet dieser die Eingabe und den Beweis. Falsche Beweise nimmt der Pr¨ ufer nicht an. Falls es einen korrekten Beweis f¨ ur die Eingabe gibt, so muß es auch einen korrekten Beweis f¨ ur die Eingabe geben, den der Pr¨ ufer stets akzeptiert.

5

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

Graphen und Algorithmen II

3SAT -Formel

Beweis (Belegung) - Beweiser (allm¨ achtig)

Eingabe J



J

(Poly in Eingabel¨ ange)

J (polynomielle Laufzeit)

J

J Pr¨ ufer

ja ⇒ Formel ist erf¨ NP J ullbar ^ J P



Formel erf¨ ullbar ⇒ ∃ Beweis: Pr¨ ufer gibt ja aus ? ja/nein Die Klasse P CP (log n, 1) l¨ aßt sich beispielsweise folgendermaßen umreißen: Gegeben sei eine Eingabe (z.B. eine 3SAT -Formel). Man stelle sich nun vor, ein “allm¨ achtiger” Beweiser k¨ onne einen Beweis von in der Eingabel¨ ange polynomieller L¨ ange f¨ ur die Eingabe finden. Wenn es nun einen Pr¨ ufer gibt, der einen beliebigen solchen Beweis pr¨ ufen kann und dabei folgenden Anforderungen gen¨ ugt, so liegt das Problem in P CP (log n, 1): Der Pr¨ ufer darf nat¨ urlich die Eingabe betrachten. Der Pr¨ ufer betrachtet nur O(1) viele Bits des Beweises. Der Pr¨ ufer betrachtet O(log n) viele zus¨ atzliche zuf¨ allige Bits. Der Pr¨ ufer arbeitet in polynomieller Zeit. Falls der Beweis korrekt ist, so gibt der Pr¨ ufer auf jeden Fall “ja” aus, der Pr¨ ufer kann jedoch falsche Beweise annehmen. Falls ein Beweis falsch ist, so muß der Pr¨ ufer mit einer Wahrscheinlichkeit von 3/4 “nein” ausgeben. Falls es einen korrekten Beweis f¨ ur die Eingabe gibt, so muß es auch einen korrekten Beweis f¨ ur die Eingabe geben, den der Pr¨ ufer stets akzeptiert. Beweis - Beweiser (allm¨ achtig)

Eingabe J

-

J

J P CP (log n, 1) J

J

J ^ J -

Pr¨ ufer P















(Poly in Eingabel¨ ange)

O(1) Bits

ja ⇒ Formel ist wahrscheinlich erf¨ ullbar

Formel erf¨ ullbar ⇒ ∃ Beweis: Pr¨ ufer gibt ja aus ? ja/nein “property testing” ist ein Werkzeug in dieser Konstellation.

log n zuf¨ allige Bits

6

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

Graphen und Algorithmen II

2.2 P und N P 2.2.1 Die Turingmaschine ? 1

. . . Eingabe nur lesen ? 0

Steuereinheit ? 1

... . . . Ausgabe nur schreiben

Definition. Eine k-Band Turingmaschine TM mit Ein- und Ausgabe ist ein Tupel (K, Σ, δ, s), wobei: K 6= ∅ ist eine Menge von Zust¨anden. Σ ist ein Alphabet, also eine endliche Menge von Symbolen, mit Σ ∩ K = ∅ und zwei besonderen Symbolen t (“blank”), . (“start”) ∈ Σ. s ∈ K ist ein Anfangszustand. δ : K × Σk → (K ∪ {halt, ja, nein} × (Σ × {←, −, →})k mit halt, ja, nein, →, −, ← ∈ / K ∪ Σ. Ist δ(q, σ1 , . . . , σk ) = (p, ρ1 , D1 , . . . , ρk , Dk ), so gilt: 1. ist σi = ., so ist ρi = . und Di = →. 2. ρ1 = σ1 (das Eingabeband wird nicht ¨ uberschrieben) 3. Dk 6= ← (auf dem Ausgabeband wird nicht “zur¨ uckgegangen”) 4. Falls σ1 = t, so gilt D1 = ← (die TM kann nicht ¨ uber das Ende der Eingabe hinaus laufen.) Definition. Eine Konfiguration einer Turingmaschine M ist ein (2k + 1)-Tupel (q, w1 , u1 , . . . , wk , uk ) mit q ∈ K und wi , ui ∈ Σ∗ . Dabei ist q ein Zustand, wi der Inhalt des i-ten Bandes bis einschließlich zum Schreib-Lesekopf und u i der Inhalt des i-ten Bandes nach dem Schreib-Lesekopf. Definition. Seien c = (q, w1 , u1 , . . . , wk , uk ) und c0 = (q 0 , w10 , u01 , . . . , wk0 , u0k ) zwei M

Konfigurationen. Dann ¨ uberf¨ uhrt M c in c0 (c → c0 ), wenn: Sei σi das letzte Symbol in wi , und gelte δ(q, σ1 , . . . , σk ) = (p, ρ1 , D1 , . . . , ρk , Dk ), so haben wir: q0 = p f¨ ur alle i = 1, . . . , k gilt:

7

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

Graphen und Algorithmen II

– wenn Di = → , so entsteht wi0 aus wi durch Ersetzen des letzten Symbols von wi durch ρi und Anh¨angen des ersten Symbols von ui , falls ui nicht das leere Wort ist, bzw. Anh¨angen von t, falls ui leer ist; u0i ist ui ohne das erste Symbol, – wenn Di = ← , so entsteht wi0 aus wi durch Weglassen des letzten Symbols, und u0i entsteht aus ui durch Anf¨ ugen von ρi an den Anfang von ui , – wenn Di = − , so ist u0i = ui und wi0 entsteht aus wi durch Ersetzen des letzten Symbols von wi durch ρi . ? .· · · 1 0 1  w   i

ui

? δ  - q0 ··· q .· · · 1 1 1 (1, →)    wi 

··· ui

Die Turingmaschine M u uhrt eine Konfiguration c0 in l Schritten in eine Konfigu¨berf¨ M M M ration cl , falls es Konfigurationen c1 , . . . , cl−1 gibt, so daß: c0 → c1 → c2 . . . → cl . Wir M∗

Ml

Ml

schreiben daf¨ ur c0 → cl . Wir schreiben c → c0 , falls es eine Zahl l gibt, so daß c → c0 . Eine k-Band-Turingmaschine M beginnt ihre Berechnung in der Konfiguration (s, ., x, ., ε, . . . , ., ε), wobei: s = Startzustand x ∈ (Σ\{t})∗ Eingabe ε = leeres Wort . = Startsymbol Nun gelten folgende Regeln: M∗

Falls (s, ., x, ., ε, . . . ., ε) → (ja, u1 , w1 , . . . , uk , wk ), so akzeptiert M x: M (x) = ja. M∗

Falls (s, ., x, ., ε, . . . , ., ε) → (nein, u1 , w1 , . . . , uk , wk ), so lehnt M x ab: M (x) = nein. M∗

Falls (s, ., x, ., ε, . . . , ., ε) → (halt, u1 , w1 , . . . , uk , wk ), so sei M (x) = y, wobei y das Wort ist, das aus uk wk durch Weglassen des Startsymbols . sowie der am Ende stehenden t-Symbole entsteht. Falls keiner dieser F¨ alle eintritt, divergiert M auf der Eingabe x: M (x) = %. Mt

Falls (s, ., x, ., ε, . . . , ., ε) → (H, u1 , w1 , . . . , uk , wk ), wobei H ∈ {ja, nein, halt}, so ist die Laufzeit von M (x) t. Definition. Sei f : N → N eine Funktion. Die Laufzeit von M ist durch f beschr¨ankt, falls f¨ ur alle Eingaben x gilt: die Laufzeit von M (x) ist h¨ochstens f (|x|).

8

Vorlesung 20.04.04

Graphen und Algorithmen II

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

Pk−1 Der Platzbedarf von M bei Eingabe x ist i=2 |ui | + |wi |, wobei u1 , w1 , . . . , uk , wk die Bandinhalte am Ende der Berechnung sind (mit t-Symbolen). Wie zuvor definiert man, daß M durch f : N → N beschr¨ ankten Platzbedarf hat. Definition. Sei L ⊂ (Σ\{t})∗ eine Sprache. Dann entscheidet M L, falls f¨ ur alle x ∈ (Σ\{t})∗ gilt: x ∈ L ⇒ M (x) = ja x∈ / L ⇒ M (x) = nein 2.2.2 Sprachen und Sprachklassen Sei f : N → N eine Funktion. Dann ist T IM E(f ) = {L ⊂ (Σ\{t})∗ |∃ TM M, die L entscheidet und durch O(f ) beschr¨ ankte Laufzeit hat.}, SP ACE(f ) = {L ⊂ (Σ\{t})∗ |∃ TM M : M entscheidet L, Platzbedarf von M ist durch O(f ) beschr¨ ankt.}, S P = c≥1 T IM E(nc), S P SP ACE = c≥1 SP ACE(nc ), L = SP ACE(log n).

Sei L ⊂ (Σ\{t})∗ . Dann ist L ∈ N P genau dann, wenn Folgendes gilt: Es gibt eine Zahl l ∈ N und eine TM M mit folgenden Eigenschaften: 1. Die Laufzeit von M ist polynomiell. 2. Zu jedem x ∈ L gibt es ein y ∈ (Σ\{t})∗ mit |y| ≤ |x|l , so daß M (x t y) = ja. 3. Ist x ∈ (Σ\{t})∗ \L, so gilt f¨ ur alle y ∈ (Σ\{t})∗ , daß M (x t y) = nein. M heißt Polynomzeit-Verifizierer f¨ ur L. 2.2.3 Reduktion Definition. Eine Abbildung R : (Σ\{t})∗ → (Σ\{t})∗ heißt in Polynomzeit berechenbar, falls es eine polynomiell zeitbeschr¨ankte TM M gibt, so daß f¨ ur alle x ∈ (Σ\{t})∗ gilt: M (x) = R(x) Definition. Seien L1 , L2 ⊂ (Σ\{t})∗ . L1 ist auf L2 P -reduzierbar (kurz: reduzierbar), falls es eine Abbildung R : (Σ\{t})∗ → (Σ\{t})∗ gibt, so daß gilt: 1. R ist in Polynomzeit berechenbar. 2. F¨ ur alle x ∈ (Σ\{t})∗ gilt: R(x) ∈ L2 ⇔ x ∈ L1 .

9

Graphen und Algorithmen II

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

R heißt dann eine Reduktion von L1 auf L2 . Eine Sprache heißt N P -schwer, falls jede Sprache L0 in N P auf L reduzierbar ist. L heißt N P -vollst¨ andig, falls L ∈ N P und L N P -schwer ist. Beispiele f¨ ur N P -vollst¨ andige Sprachen: 1. SAT = Sprache aller erf¨ ullbaren aussagenlogischen Ausdr¨ ucke. 2. 3SAT = Sprache der erf¨ ullbaren aussagenlogischen Ausdr¨ ucke in 3CN F ϕ = C1 ∧ C2 ∧ . . . ∧ Cm ; Ci = L1i ∨ L2i ∨ L3i , wobei Li = Variable oder negierte Variable 3. E3SAT : wie 3SAT , aber in jeder Klausel kommen 3 verschiedene Variablen vor. 4. 3-F¨ arbbarkeit von Graphen.

2.3 Grundbegriffe der Wahrscheinlichkeitstheorie 2.3.1 Wahrscheinlichkeitsr¨ aume und Ereignisse Definition. Ein Wahrscheinlichkeitsraum P ist ein Paar (Ω, P ), wobei Ω 6= ∅ eine endliche Menge ist und P : Ω → [0, 1] so, daß ω∈Ω P (ω) = 1.

Definition. P Die Teilmengen von Ω heißen Ereignisse. Ist A ein Ereignis, so heißt P (A) = ω∈A P (ω) die Wahrscheinlichkeit von A.

Konsequenzen aus der Definition: Sind A und B Ereignisse, so gilt: 1. P (Ω\A) = 1 − P (A) 2. A ⊂ B ⇒ P (A) ≤ P (B) 3. P (A\B) = P (A) − P (A ∩ B) 4. P (A ∪ B) + P (A ∩ B) = P (A) + P (B) also: A ∩ B = ∅ ⇒ P (A ∪ B) = P (A) + P (B) und in jedem Fall: P (A ∪ B) ≤ P (A) + P (B) Beispiele:

Ω = {1, . . . , 6}, P (ω) = 1/6 ∀ ω ∈ Ω. A = {2, 4, 6} =“gerade Zahl”. P (A) = 16 + 61 + 61 = 12 . Ω = {0, 1}, P (1) = p, P (0) = 1 − p, “M¨ unzwurf mit Erfolgswahrscheinlichkeit p”. p = 1/2: “fairer M¨ unzwurf” Ist Ω eine endliche Menge, so heißt die Abbildung P : Ω → [0, 1], ω 7→ 1/#Ω die Gleichverteilung auf Ω.

10

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

Graphen und Algorithmen II

Definition. Sei (Ω, P ) ein Wahrscheinlichkeitsraum. Seien A, B ⊂ Ω. A, B heißen unabh¨angig, falls P (A ∩ B) = P (A)P (B). Sind allgemein A1 , . . . , An Ereignisse, so heißen diese unabh¨angig, falls f¨ ur alle J ⊂ {1, . . . , n} gilt: Y \ P (Aj ). Aj ) = P( j∈J

j∈J

Definition. Der Produktraum von zwei Wahrscheinlichkeitsr¨aumen (Ω1 , P1 ), (Ω2 , P2 ): (Ω, P ) = (Ω1 , P1 ) × (Ω2 , P2 ) ist definiert durch: Ω = Ω 1 × Ω2 P ((ω1 , ω2 )) = P1 (ω1 ) · P2 (ω2 ) Sind A ⊂ Ω1 , B ⊂ Ω2 Ereignisse, so ist P (A × B) = P1 (A)P2 (B) ⇒ P (A × Ω2 ) = P1 (A) und P (Ω1 × B) = P2 (B) Also: Die Ereignisse A × Ω2 ; Ω1 × B sind unabh¨ angig in (Ω, P ). Beispiel: W¨ urfeln mit 2 unabh¨ angigen W¨ urfeln. Ω = {1, . . . , 6} × {1, . . . , 6}; P ((ω1 , ω2 )) = 1/36 ∀ ω1 , ω2 2.3.2 Zufallsvariablen Definition. Sei (Ω, P ) ein Wahrscheinlichkeitsraum. Eine Zufallsvariable X auf (Ω, P ) ist eine Abbildung X : Ω → R (“Meßger¨at”). P Definition. Der Erwartungswert von X ist E[X] = ω∈Ω X(ω)P (ω).

Ist Y : Ω → R eine weitere Zufallsvariable, so gilt E[X + Y ] = E[X] + E[Y ], wobei X + Y die Zufallsvariable X + Y : Ω → R; ω 7→ X(ω) + Y (ω) ist. Ist λ ∈ R, so ist E[λX] = λE[X], wobei λX die Zufallsvariable λX : Ω → R; ω 7→ λX(ω) ist. Dieses Verhalten wird auch “Linearit¨ at des Erwartungswertes” genannt. Beispiel: Ω = {1, . . . , 6}, P (ω) = 1/6 ∀ ω X(ω) = ω 2 ⇒ E[X] =

1 91 (1 + 4 + 9 + 16 + 25 + 36) = 6 6

Die Markoff-Ungleichung Sei X : Ω → R≥0 (= {x ∈ R|x ≥ 0}) eine Zufallsvariable. Dann gilt: Pr(X ≥ t · E[X]) ≤ 1/t f¨ ur t > 0. Definition. Sei X : Ω → R eine Zufallsvariable. Die Varianz von X ist Var(X) = E[X 2 ] − (E[X])2 = E[(X − E[X])2 ]. Es gilt: Var(X) ≥ 0. Sind X, Y unabh¨ angige Zufallsvariablen, so ist Var(X + Y ) = Var(X) + Var(Y ) und ist λ ∈ R, so ist Var(λX) = λ2 Var(X). Die Tschebyscheff-Ungleichung Sei X : Ω → R eine Zufallsvariable. Sei t > 0. Dann gilt: Pr(|X − E[X]| > t) ≤ Var(X)/t2 .

11

Vorlesung 22.04.04

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

Graphen und Algorithmen II

2.4 Polynome u orpern ¨ber endlichen K¨ Definition. Eine abelsche Gruppe ist ein Paar (G, ◦), wobei G 6= ∅ eine Menge ist und ◦ : G × G → G, (g, h) 7→ g ◦ h, mit folgenden Eigenschaften: 1. ∀ x, y, z ∈ G gilt x ◦ (y ◦ z) = (x ◦ y) ◦ z 2. ∀ x, y ∈ G gilt x ◦ y = y ◦ x 3. ∃ e ∈ G ∀ x ∈ G gilt e ◦ x = x. e heißt neutrales Element 4. ∀ x ∈ G ∃ y ∈ G, so daß y ◦ x = e. y heißt zu x inverses Element. Beispiel: (Z, +); neutrales Element 0, Inverses zu x ∈ Z ist −x. Definition. Ein K¨orper ist ein Tripel (K, +, ◦), so daß Folgendes gilt: 1. (K, +) ist eine abelsche Gruppe mit neutralem Element 0. Das Inverse von x in (K, +) wird mit −x bezeichnet. 2. (K \ {0}, ◦) ist eine abelsche Gruppe mit neutralem Element 1. Das Inverse von x in (K\{0}, ◦) wird mit x−1 bezeichnet. 3. F¨ ur alle x, y, z ∈ K gilt: x ◦ (y + z) = (x ◦ y) + (x ◦ z), wobei wir f¨ ur alle x ∈ K definieren 0 ◦ x = x ◦ 0 = 0. Beispiel: (Q, +, ·) und (R, +, ·) F¨ ur die Vorlesung sind endliche K¨ orper relevant. Sei dazu p eine Primzahl. Dann definieren wir einen K¨ orper Fp mit den Elementen {0, 1, . . . , p − 1}: Sind x, y ∈ {0, . . . , p − 1}, so ist x +p y = Rest von x + y bei Division durch p. x ·p y = Rest von x · y bei Division durch p. Wir schreiben + statt +p und · statt ·p . Beispiel: p = 5 x+y 0 1 2 3 4

0 0 1 2 3 4

1 1 2 3 4 0

2 2 3 4 0 1

3 3 4 0 1 2

x·y 0 1 2 3 4

4 4 0 1 2 3

0 0 0 0 0 0

1 0 1 2 3 4

2 0 2 4 1 3

3 0 3 1 4 2

4 0 4 3 2 1

Absicht: Ausdr¨ ucke wie 2X − 7X 2 + X 3 + 1 oder X12 X2 + 9X15 + 7X22 − 3 sollen eine Bedeutung bekommen. Sei K ein K¨ orper, und seien X1 , . . . , Xn ∈ / K n verschiedene Symbole. Diese nennen wir Variablen. Es soll definiert werden, was ein Polynom u ¨ber K in den Variablen X1 , . . . , Xn ist.

12

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

Graphen und Algorithmen II

Definition. Sei N = {(ν1 , . . . , νn ) | ν1 , . . . , νn ∈ N0 }. Ein Polynom ¨ uber K in X1 , . . . , Xn ist eine Abbildung f : N → K, so daß es nur endlich viele ν ∈ N gibt mit f (ν) 6= 0. Seien f, g : N → K Polynome. Dann definieren wir ein Polynom h : N → K durch h(ν) = f (ν) + g(ν). h heißt die Summe von f und g. Man schreibt h = f + g. Das Polynom k : N → K mit k(ν) = −f (ν) heißt das Negative von f . (Schreibweise: −f ) Das Produkt von f, g ist das Polynom l : N → K mit X f (ν 0 ) · g(ν 00 ). l(ν) = 0 (ν10 ,...,νn )∈N 00 (ν100 ,...,νn )∈N mit νi =νi0 +νi00 ∀i

Man schreibt l = f · g. Wir wollen nun Polynome etwas intuitiver aufschreiben. Sei f : N → K das Polynom mit f (0, . . . , 0) = a ∈ K , f (ν) = 0 ∀ ν 6= (0, . . . , 0). Dann schreiben wir kurz f = a. Ist f : N → K das Polynom mit f (0, . . . , 0, 1, 0 , . . . , 0) = 1 ↑

i−teStelle

und f (ν) = 0 f¨ ur alle anderen ν ∈ N , so schreiben wir kurz f = Xi (i ∈ {1, . . . , n}). Sei f : N → K, so daß f (ν 0 ) = 1 f¨ ur ein ν 0 ∈ N , und f (ν) = 0 ∀ ν 6= ν 0 . 0 0 0 Sei ν = (ν1 , . . . , νn ). Dann gilt: n Y ν0 f= Xi i . i=1

Daher gilt nun f¨ ur jedes Polynom f : N → K, daß f=

X

ν∈N

f (ν) · |{z} ∈K

n Y

Xiνi .

i=1

Die Elemente f (ν1 , . . . , νn ) ∈ K heißen Koeffizienten des Polynoms f . Mit K[X1 , . . . , Xn ] wird die Menge aller Polynome inPX1 , . . . , Xn u ¨ber K bezeichnet. Der Grad oder totale Grad von f ist Gradf = max{ ni=1 νi | f (ν1 , . . . , νn ) 6= 0}. Der Grad von f in Xi ist GradXi f = max{νi | f (ν1 , . . . , νn ) 6= 0}.

13

Vorlesung 27.04.04

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

Graphen und Algorithmen II

Beispiel: K = F7 f (X1 , X2 , X3 ) = 3X12 X23 X35 + 2X12 X3 g(X1 , X2 , X3 ) = X17 + 2X2 X3 + 6X12 X3 f + g = X17 + 3X12 X23 X35 + 2X2 X3 + 1X12 X3 f ·g

= [3X12 X23 X35 + 2X12 X3 ][X17 + 2X2 X3 + 6X12 X3 ] = 3X12 X23 X35 [X17 + 2X2 X3 + 6X12 X3 ] + 2X12 X3 [X17 + 2X2 X3 + 6X12 X3 ] = 3X19 X23 X35 + 6X12 X24 X36 + 4X14 X23 X36 + 2X19 X3 + 4X12 X2 X32 + 5X14 X32

Sei f ∈ K[X1 , . . . , Xn ]. Seien g1 , . . . , gn ∈ K[X1 , . . . , Xn ]. Dann definieren wir f (g1 , . . . , gn ) =

X

ν1 ,...,νn

f (ν1 , . . . , νn ) ·

n Y

giνi .

i=1

Insbesondere f¨ uhrt jedes f ∈ K[X1 , . . . , Xn ] auf eine Abbildung Ef : K n → K, (a1 , . . . , an ) 7→ f (a1 , . . . , an ). Die Abbildung Ef bezeichnen wir oft kurz mit f . Beispiel: Betrachte den K¨ orper F2 . Seien f, g ∈ F2 [X] mit f (X) = 0 und g(X) = X 2 + X. Dann gilt: Ef = Eg = 0. Sei K ein K¨ orper. Die Elemente von K m , m ∈ N, interpretieren wir als Vektoren, die komponentenweise addiert und mit Skalaren aus K multipliziert werden. Eine Abbildung ϕ : K m → K n heißt linear, falls f¨ ur alle x, y ∈ K m und λ ∈ K gilt: ϕ(x + y) = ϕ(x) + ϕ(y) und ϕ(λx) = λϕ(x). Lemma 1. Sei F ein endlicher K¨orper. Sei f ∈ F [X1 , . . . , Xm ] ein Polynom, welches Grad ≤ d in jeder Variablen X1 , . . . , Xm hat. Eine Nullstelle von f ist ein Punkt x ∈ F m mit f (x) = 0. Dann hat f h¨ochstens md#F m−1 Nullstellen. Beweis:. Beweis durch Induktion nach m: Ind. Anfang: Es sei m = 1. Dann hat f ∈ F [X1 ] maximal d = md#F m−1 Nullstellen. Ind. Vor.: f ∈ F [X1 , . . . , Xm ] habe h¨ ochstens md#F m−1 Nullstellen. Ind. Beh.: Alle f ∈ F [X1 , . . . , Xm+1 ] haben maximal (m + 1)d#F m Nullstellen. Jedes Polynom f ∈ F [X1 , . . . , Xm+1 ] ist darstellbar als (Ordnen nach Potenzen von d Xm+1 ): f = ad Xm+1 + . . . + a1 Xm+1 + a0 , wobei gilt a0 , . . . , ad ∈ F [X1 , . . . , Xm ]. Sei z ∈ F m : f (z, y) = 0 falls: 1. a0 (z) = a1 (z) = . . . = ad (z) = 0. Da jedes ai nach Ind.Vor. maximal md#F m−1 Nullstellen hat, kann es maximal md#F m−1 solche Punkte z ∈ F m geben mit a0 (z) = a1 (z) = . . . = ad (z) = 0. Da in diesem Fall y ∈ F beliebig gew¨ ahlt werden kann, gibt es also #F md#F m−1 Punkte x ∈ F m+1 mit f (x) = 0.

14

Graphen und Algorithmen II

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

2. ∃ ai mit ai (z) 6= 0. Wir w¨ ahlen nun z ∈ F m fix: Damit reduzieren sich alle ai zu d festen a0 (z), . . . , ad (z) ∈ F und somit fz = ad (z)Xm+1 +. . .+a1 (z)Xm+1 +a0 (z) auf ein Polynom in der Variable Xm+1 . fz hat maximal d Nullstellen. Da es #F m verschiedene z ∈ F m gibt, kann es maximal d#F m solcher Nullstellen geben. Zusammenfassend erhalten wir: md#F m + d#F m = (m + 1)d#F m Nullstellen. Damit ist die Behauptung bewiesen. Lemma 2. Sei F ein endlicher K¨orper. Seien (a1 , b1 ), . . . , (ak , bk ) ∈ F 2 paarweise verschieden. Es gibt ein eindeutig bestimmtes Polynom f ∈ F [X] vom Grad k − 1, so daß f (ai ) = bi f¨ ur i = 1, . . . , k (das Polynom durchl¨auft die Punkte (ai , bi )). Beweis:. Zu jedem x ∈ F gibt es per Definition ein inverses Element −x bzgl. der Addition. Wir wollen im Folgenden f¨ ur y + (−x) verk¨ urzend schreiben: y − x. Ebenso bezeichne 1/x das zu x ∈ F bzgl. der Multiplikation inverse Element. Wir definieren: pn f

X − a1 X − an−1 X − an+1 X − ak ... ... an − a 1 an − an−1 an − an+1 an − a k := b1 p1 + . . . + bk pk :=

Folgerungen: f¨ ur m ∈ {1, . . . , k} mit m 6= n gilt: pn (am ) = 0. pn (an ) = 1. pn hat Grad k − 1, da es aus genau k − 1 Termen der Form X − aj /(an − aj) (vom Grad 1) besteht. f¨ ur i ∈ {1, . . . , k} gilt: f (ai ) = bi . da alle pn Grad k − 1 haben und f sich additiv aus solchen zusammensetzt, hat f den Grad k − 1. Die letzten beiden Punkte zeigen, daß f die geforderten Voraussetzungen erf¨ ullt. Bleibt die Eindeutigkeit zu zeigen: Wir nehmen an, es g¨ abe zwei verschiedene Polynome f 6= g vom Grad k − 1, so daß f (ai ) = g(ai ) = bi ∀ i ∈ {1, . . . , k}. Somit stimmen f und g an k verschiedenen Punkten u ur ¨berein. Jedoch kann es maximal k − 1 Punkte x geben, f¨ die gilt: f (x) = g(x). Widerspruch! Somit gilt f = g, weshalb die Funktion eindeutig ist. Lemma 3. Sei F ein endlicher K¨orper mit #F ≥ 10d. Sei g : Fm → F eine Abbildung. Dann gibt es genau dann ein Polynom f ∈ F[X1 , . . . , Xm ] vom (totalen) Grad ≤ d, so daß f (x) = g(x) f¨ ur alle x ∈ Fm , wenn folgende Bedingung erf¨ ullt ist: m Sind b, s ∈ F , so gibt es ein Polynom fb,s ∈ F[X] vom Grad ≤ d, so daß f¨ ur alle t ∈ F gilt fb,s (t) = g(b + ts).

15

¨ 2 EINFUHRUNG UND WIEDERHOLUNG

Graphen und Algorithmen II

Beweis:. ⇒ ist klar. ⇐ Seien c0 , . . . , cd ∈ F d + 1 verschiedene Elemente. Durch Induktion u ¨ber k folgt ∃ gi Polynom vom Grad ≤ d, so daß gi (X2 , . . . , Xk ) = g(ci , X2 , . . . , Xk ) i = 0, . . . , d. Sei ϕi ∈ F[X] ein Polynom vom Grad ≤ d, so daß  1, falls c = ci . ϕi (c) = 0, falls c = cj j 6= i p(X1 , . . . , Xk ) =

d X

ϕi (X1 )gi (X2 , . . . , Xk ).

i=0

Wir wissen bereits, daß Gradp ≤ 2d. Wir zeigen erstmal, daß g = p. Sei u ∈ Fk−1 ein festgew¨ ahlter Punkt. Dann sind g(X, u), p(X, u) Polynome vom Grad ≤ d, (denn g(X, u) ist die Einschr¨ ankung von g auf eine Gerade gb,s mit b = (0, u), s = (1, 0), da gb,s (X) = g(b + Xs)) und g(ci , u) = p(ci , u) f¨ ur i = 0, . . . , d. Weil p(ci , u) =

d X

ϕj (ci )gj (u) = gi (u) = g(ci , u),

j=0

stimmen p(X, u), g(X, u) in d + 1 Punkten u ¨berein. ⇒ p(X, u) = g(X, u). ⇒ p(x, u) = g(x, u) ∀ x ∈ F. Da u beliebig gew¨ ahlt war, ist g = p. Es bleibt nur noch zu zeigen, daß Gradp ≤ d. p ist darstellbar in der Form X αν X1ν1 . . . Xkνk , p= ν∈N2d

Pk wobei N2d = {ν = (ν1 , . . . , νk ) | i=1 νi ≤ 2d}. F¨ ur jedes s ∈ Fk ist nun die Einschr¨ ankung p0,s von p auf die Gerade {0 + ts | t ∈ F} ein Polynom vom Grad ≤ d. Außerdem gilt: p0,s (t) = p(0 + ts) = p(ts1 , . . . , tsk ) =

2d X j=0

Definiere βj =

P

ν∈N2d P νi =j

tj

X

ν∈N2d P νi =j

αν sν11 . . . sνkk , ∀ s ∈ Fk ∀ t ∈ F.

αν sν11 . . . sνkk . Da p0,s ein Polynom vom Grad ≤ d ist, folgt

βj = 0 ∀ j > d. Somit hat das Polynom X αν X1ν1 . . . Xkνk ν∈N2d P νi =j

f¨ ur j > d #F Nullstellen und Grad ≤ 2d. P ⇒ Es ist das Nullpolynom. (#F > 10d > 2d) ⇒ αν = 0 ∀ ν mit νi > d. ⇒ p hat Grad ≤ d.

16

Graphen und Algorithmen II

3 FORMULIERUNG DES P CP -THEOREMS

3 Formulierung des P CP -Theorems 3.1 Schaltnetze Definition. Ein boolesches Schaltnetz ist ein gerichteter Graph G = (V, E) mit V = {1, . . . , n}, E ⊂ V × V , (v, v) ∈ / E f¨ ur alle v ∈ V zusammen mit einer Menge X = {x1 , . . . , xk } von Variablen und einer Abbildung s : V → {¬, ∧, ∨, 0, 1} ∪ X, so daß folgende Bedingungen erf¨ ullt sind: 1. Ist (v, w) ∈ E, so ist v < w. (kreisfrei) 2. Ist s(v) ∈ {0, 1} ∪ X, so ist der Eingangsgrad von v (d.h. die Zahl der Kanten (w, v) ∈ E, w ∈ V ) gleich 0. 3. Ist s(v) = ¬, so ist der Eingangsgrad von v 1. 4. Ist s(v) ∈ {∨, ∧}, dann ist der Eingangsgrad von v 2. Die Knoten v mit s(v) ∈ X heißen Eing¨ ange, der Knoten n heißt Ausgang. Sei T : X → {0, 1} eine Belegung der Variablen. Sei v ∈ V . Dann definieren wir T (v) induktiv: Ist s(v) ∈ X, so ist T (v) = T (s(v)). Ist s(v) ∈ {0, 1}, so ist T (v) = s(v). Ist s(v) = ¬ und ist w ∈ V so, daß (w, v) ∈ E, dann ist T (v) = ¬T (w). Ist s(v) = ∨ und sind x, y ∈ V so, daß (x, v), (y, v) ∈ E, x 6= y, dann ist T (v) = T (x) ∨ T (y). Analog f¨ ur s(v) = ∧. Schließlich ist T (G) = T (n). T erf¨ ullt das Schaltnetz, falls T (G) = 1. Schaltnetzwert-Problem: Gegeben sind T und C, wobei C ein Schaltnetz und T eine Belegung ist. Berechne den Wert T (C). Schaltnetz-Erf¨ ullbarkeit: Hat ein gegebenes Schaltnetz eine erf¨ ullende Belegung?  x1 x2 x3 0 1  J J



? J^ J^    J J 



∧ ¬ ∨    S  S  Sw    S /  - ∧ ∨   

17

3 FORMULIERUNG DES P CP -THEOREMS

Graphen und Algorithmen II

3.2 Das P CP -Theorem Definition. Seien r, q : N → N Funktionen. Sei L ⊂ {0, 1}∗. Ein (r, q)-Verifizierer f¨ ur L ist eine polynomialzeitbeschr¨ankte Turingmaschine M mit folgenden Eigenschaften: Sei x ∈ {0, 1}∗ und sei y ∈ {0, 1}r(|x|). Dann besteht die Ausgabe von M bei Eingabe x t y aus 1. einer Folge Q1 , . . . , Qν , wobei ν = q(|x|), von Bin¨arzahlen (durch t getrennt) und 2. einem Schaltnetz Cx,y , dessen Gr¨oße polynomiell in q(|x|) ist mit q(|x|) Eing¨angen, so daß folgende Bedingungen erf¨ ullt sind: Vollst¨ andigkeit: Falls x ∈ L, so gibt es ein Wort π in {0, 1}∗, π = (π1 , . . . , π|π| ), so daß f¨ ur alle y ∈ {0, 1}r(|x|) gilt: Cx,y (πQ1 , . . . , πQν ) = 1 (f¨ ur l > |π| setze πl = 0). Korrektheit: Falls es ein π ∈ {0, 1}∗ gibt, so daß Pr

y∈{0,1}r(|x|)

[Cx,y (πQ1 , . . . , πQν ) = 1] >

1 , 4

so gilt x ∈ L. Wir nennen π einen Beweis. M akzeptiert (x, y, π), falls Cx,y (πQ1 , . . . , πQν ) = 1. Sonst lehnt M (x, y, π) ab.

x = Eingabe

-

y = r(|x|) Z-Bits -

Verifizierer M

Anfrage Q1 , . . . , Qν

- Schaltnetz C = Cxy

πQ 1 @ R @ 

πQ 2

. . . πQ ν  

?  C  ? 0/1

Wir definieren nun die Klasse P CP (r, q) als die Menge aller Sprachen L, die einen (O(r), O(q))-Verifizierer haben. Satz 1. (P CP -Theorem) N P = P CP (log n, 1) (n = Eingabel¨ange, P CP bedeutet “probabilistically checkable proofs”) Aus beweistechnischen Gr¨ unden betrachten wir zus¨ atzlich die Klassen P CP (r, b, q), wobei r, b, q : N → N. Definition. Ein (r, b, q)-Verifizierer f¨ ur eine Sprache L ⊂ {0, 1}∗ ist eine Polynomialzeit-Turingmaschine M , so daß gilt: Ist x ∈ {0, 1}∗ und y ∈ {0, 1}r(|x|), so gibt M auf Eingabe x t y Folgendes aus:

18

Vorlesung 29.04.04

4 N P ⊂ P CP (N 3 , 1)

Graphen und Algorithmen II

1. Eine Folge von ν = q(|x|) Bin¨arzahlen q1 , . . . , qν . 2. Ein Schaltnetz C mit b(|x|) · q(|x|) Eing¨angen und poly(b(|x|) + q(|x|)) Knoten, so daß gilt: Vollst¨ andigkeit: Ist x ∈ L, so gibt es ein π = (π1 . . . πN ), N ∈ N mit πi ∈ {0, 1}b(|x|), so daß f¨ ur alle y ∈ {0, 1}r(|x|) gilt: C(πq1 , . . . , πqν ) = 1. Korrektheit: Falls x ∈ {0, 1}∗ so ist, daß es ein π wie oben gibt mit Pry∈{0,1}r(|x|) [C(πq1 , . . . , πqν ) = 1] > 1/4, so ist x ∈ L. P CP (r, b, q) ist dann die Menge aller Sprachen, die einen (O(r), O(b), O(q))-Verifizierer besitzen. Offenbar gilt: P CP (r, b, q) ⊂ P CP (r, b · q). Notation: 1. Ist f : N → N, so bezeichnet poly(f ) eine Abbildung N → N, die durch ein Polynom in f beschr¨ ankt ist. (poly(f ) = f O(1) ) 2. Pry∈Ω [A] bezeichnet die Wahrscheinlichkeit des Ereignisses A, wenn y zuf¨ allig gew¨ ahlt wird. ad 1) Seien f, g : N → N Abbildungen. Dann gilt g = poly(f ), falls ∃ c, d > 0, n0 ∈ N, so daß ∀ n ≥ n0 : g(n) ≤ c · f (n)d . ad 2) gleichverteilt und unabh¨ angig, wenn nichts anderes gesagt. P CP (r, b, q)

P CP (r, q) -

x

Verifizierer M -

y

-

... ? C

π Bits - 0/1

x y

-

Verifizierer M -

-

... ... ... ... ? C

b(|x|) Bits π - 0/1

4 N P ⊂ P CP (n3 , 1) E3SAT : Eingabe: 3SAT -Formel, so daß jede Klausel 3 verschiedene Variablen enth¨ alt (verboten: (x ∨ x ∨ y), (x ∨ x ∨ z), . . .). Problem: Entscheiden, ob erf¨ ullbar. 3

Idee: Konstruktion eines “transparenten Langbeweises”. Dieser hat die L¨ ange 2Θ(n ) .

19

4 N P ⊂ P CP (N 3 , 1)

Graphen und Algorithmen II

4.1 Arithmetisierung boolescher Formeln Sei ϕ = C1 ∧ . . . ∧ Cm eine E3SAT -Formel mit Klauseln C1 , . . . , Cm , in der die booleschen Variablen x1 , . . . , xn vorkommen. Seien X1 , . . . , Xn Unbestimmte. 1.Versuch: Wir ordnen ϕ ein Polynom pϕ ∈ F2 [X1 , . . . , Xn ] zu. Dies geschieht induktiv u ¨ber den Aufbau der Formel ϕ. F¨ ur eine Variable xi definieren wir pxi = 1 − Xi . F¨ ur eine negierte Variable xi setzen wir pxi = Xi . Zu einer Klausel C = L1 ∨ L2 ∨ L3 aus Literalen L1 , L2 , L3 setze pC = pL1 · pL2 · pL3 . Schließlich ist f¨ ur ϕ = C1 ∧ . . . ∧ Cm pϕ =

m P

p Ci .

i=1

pϕ ist ein Polynom vom Grad 3. Ist a1 , . . . , an eine Belegung der booleschen Variablen x1 , . . . , xn mit true = 1 und f alse = 0, die die Formel erf¨ ullt, so gilt: pϕ (a1 , . . . , an ) = 0 Falls hingegen a1 , . . . , an keine erf¨ ullende Belegung ist, so kann es trotzdem passieren, daß pϕ (a1 , . . . , an ) = 0. 2.Versuch: Sei r ∈ {0, 1}m. Wir definieren Polynome pϕ,r , d.h. wir ordnen jedem ϕ eine Familie von Polynomen zu. Es sei r = (r1 , . . . , rm ). Dann setzen wir pϕ,r :=

m X i=1

ri · p Ci .

Ist (a1 , . . . , an ) eine erf¨ ullende Belegung von ϕ, so gilt: pϕ,r (a1 , . . . , an ) = 0 ∀ r. Lemma 4. Ist z = (z1 , . . . , zm ) ∈ Fm 2 , z 6= 0, so gilt: Prm [

r∈F2

m X i=1

zi · ri = 1] =

1

1 . 2

Also: Ist (a1 , . . . , an ) keine erf¨ ullende Belegung, so gilt: Prm [pϕ,r (a1 , . . . , an ) = 1] =

r∈F2

1 Der

¨ Beweis bleibt dem Leser als Ubung u ¨ berlassen.

20

1 . 2

4 N P ⊂ P CP (N 3 , 1)

Graphen und Algorithmen II

Satz 2. Sei a = (a1 , . . . , an ) ∈ Fn2 . Dann gibt es lineare Abbildungen Aa : Fn2 → F2 , 2 Ba : Fn2 → F2 , 3 Ca : Fn2 → F2 ,

so daß f¨ ur jedes Polynom p ∈ F2 [X1 . . . Xn ] vom Grad 3 Folgendes gilt: Es gibt αp ∈ F2 , 2 3 qp,1 ∈ Fn2 , qp,2 ∈ Fn2 , qp,3 ∈ Fn2 , welche nur von p abh¨angen und in Zeit poly(n) berechnet werden k¨onnen, so daß p(a1 , . . . , an ) = αp + Aa (qp,1 ) + Ba (qp,2 ) + Ca (qp,3 ). Beweis:. Man kann das Polynom p in 4 Terme zerlegen: X X Xi Xj + p(X1 , . . . , Xn ) = αp + Xi + i∈Ip,1

(i,j)∈Ip,2

X

Xi Xj Xk ,

(i,j,k)∈Ip,3

wobei αp ∈ F2 , Ip,1 ⊂ {1, . . . , n}, Ip,2 ⊂ {1, . . . , n}2 , Ip,3 ⊂ {1, . . . , n}3 . X X X ai aj ak . ⇒ p(a1 , . . . , an ) = αp + ai aj + ai + i∈Ip,1

(i,j,k)∈Ip,3

(i,j)∈Ip,2

Wir definieren nun 3 lineare Abbildungen Aa , Ba , Ca , welche nur von a abh¨ angen: Pn n Aa : F2 → F2 , (u1 , . . . , un ) 7→ ua, Pni=1 i i n2 ui,j ai aj , Ba : F2 → F2 , (ui,j )i,j=1...n 7→ Pni,j=1 3 Ca : Fn2 → F2 , (ui,j,k )i,j,k=1...n 7→ i,j,k=1 ui,j,k ai aj ak . (1)

(n)

Sei nun qp,1 = (qp,1 , . . . , qp,1 ) definiert durch  1 falls i ∈ Ip,1 (i) qp,1 = 0 sonst (1,1)

(n,n)

und qp,2 = (qp,2 , . . . , qp,2 ) definiert durch  1 falls (i, j) ∈ Ip,2 (i,j) qp,2 = 0 sonst und qp,3 analog. ⇒ αp , qp,1 , qp,2 , qp,3 sind in Polynomzeit berechenbar. Schließlich gilt: p(a1 , . . . , an ) = αp + Aa (qp,1 ) + Ba (qp,2 ) + Ca (qp,3 ).

Der (ideale) transparente Langbeweis π f¨ ur die Tatsache, daß a eine erf¨ ullende Belegung f¨ ur ϕ ist, besteht nun aus den Werten (Aa (u))u∈Fn2 , (Ba (u))u∈Fn2 , (Ca (u))u∈Fn3 . 2

π:

Aa 2n

Ba 2n

2

Ca 2 n 2

3

Gesamtl¨ ange von π: 2n + 2n + 2n .

21

3

2

4 N P ⊂ P CP (N 3 , 1)

Graphen und Algorithmen II

4.2 Linearit¨ atstest

Vorlesung 04.05.04

Aufgaben des Verifizierers: 1. Teste, ob π aus 3 linearen Abbildungen A, B, C besteht. 2. Teste, ob A, B, C konsistent sind, d.h. ∃ a : A = Aa ∧ B = Ba ∧ C = Ca . 3. Erf¨ ullt a die E3SAT -Instanz ϕ? Definition. Seien D, R zwei endliche Mengen. Seien f, g : D → R zwei Abbildungen und sei δ > 0, dann heißen f, g δ-nah, falls Pr [f (d) 6= g(d)] ≤ δ.

d∈D

Mit anderen Worten: #{d ∈ D|f (d) 6= g(d)} ≤ δ · #D. Lemma 5. Sei 0 < δ < 1/3. Sei g : Fm 2 → F2 eine Abbildung, so daß Pr m [g(x) + g(y) 6= g(x + y)] <

x,y∈F2

δ , 2

dann gibt es eine lineare Abbildung f : Fm 2 → F, die δ-nah an g ist. Beweis:. Zu jedem Punkt x ∈ F2m gibt es ein b ∈ F2 , so daß Pr [g(x + y) − g(y) = b] ≥

y∈Fm 2

1 . 2

Wir definieren f (x) = b. 2 Zun¨ achst wird gezeigt, daß f , g δ-nah sind: Angenommen wir h¨ atten Prx∈Fm [f (x) 6= g(x)] > δ. Weil f¨ ur alle x gilt: 2 Pr[f (x) = g(x + y) − g(y)] ≥

1 , 2

Pr[g(x + y) − g(y) 6= g(x)] >

δ . 2

y

folgt dann, daß x,y

Dies ist ein Widerspruch. ⇒ f, g sind δ-nah. Sei zu a ∈ Fm 2 Pa := Pr[f (a) = g(a + x) − g(x)] x

Behauptung: Pa ≥ 1 − δ. Aus der Annahme folgt: Pr[g(x + a + y) 6= g(x + a) + g(y)] ≤

x,y 2 falls

es mehrere b gibt, w¨ ahle eines aus

22

δ , 2

4 N P ⊂ P CP (N 3 , 1)

Graphen und Algorithmen II

Pr[g(x + a + y) 6= g(x) + g(y + a)] ≤

x,y

δ 2

⇒ 1 − δ ≤ Pr[g(x + a) + g(y) = g(x) + g(y + a)]. x,y

Also gilt: 1−δ

≤ =

Pr[g(x + a) − g(y) = g(x) + g(y + a)] X Pr[g(x + a) + g(x) = z ∧ g(y + a) + g(y) = z]

x,y

z∈F2

=

Pr[g(x + a) + g(x) = z] · Pr[g(y + a) + g(y) = z]

X

Pr[g(x + a) + g(x) = z]2

z∈F2

=

x

X

z∈F2

x

y

x

= Pa2 + (1 − Pa )2 ⇒ 1 − δ ≤ Pa2 + (1 − Pa )2

Da Pa ≥ 1/2 folgt Pa ≥ Pa2 + (1 − Pa )2 ≥ 1 − δ. Schließlich zeigen wir, daß f linear ist. Seien a, b ∈ Fm 2 . Dreimaliges Anwenden des soeben Gezeigten f¨ uhrt auf: Prx [f (a) + f (b) + g(x) 6= g(a + x) + f (b)] ≤ δ Prx [f (b) + g(a + x) 6= g(b + a + x)] ≤ δ Prx [g(a + b + x) 6= f (a + b) + g(x)] ≤ δ. ⇒ Prx [f (a) + f (b) + g(x) 6= f (a + b) + g(x)] ≤ 3δ ≤ 1 ⇒ Prx [f (a) + f (b) 6= f (a + b)] < 1 Aber die Bedingung f (a)+f (b) 6= f (a+b) ist von x unabh¨ angig ⇒ f (a)+f (b) = f (a+b) ⇒ f ist linear. Das Lemma f¨ uhrt dann auf den folgenden Test, ob eine Funktion g : Fm 2 → F2 linear ist. Linearit¨ atstest Parameter: 0 < δ <

1 3

Ausgabe: “ja”/“nein” 1. Setze k = d δ2 e (kleinste ganze Zahl ≥ 2δ )

2. F¨ ur i = 1, . . . , k : 3. 4.

w¨ ahle x, y ∈ Fm allig. 2 zuf¨

Falls g(x) + g(y) 6= g(x + y), antworte “nein”

5. antworte “ja”

23

4 N P ⊂ P CP (N 3 , 1)

Graphen und Algorithmen II

Satz 3. Sei 0 < δ < 1/3. Sei g : Fm 2 → F2 . 1. Falls g linear ist, gibt der Linearit¨atstest auf jeden Fall “ja” aus. 2. Falls g nicht δ-nah an einer linearen Abbildung Fm 2 → F2 ist, antwortet der Linearit¨atstest mit Wahrscheinlichkeit ≥ 1/2 “nein”. Beweis:.

1. trivial.

2. Nach dem Lemma 5 ist die Wahrscheinlichkeit, daß Zeile 4 nicht “nein” antwortet, h¨ ochstens 1−δ/2. Die Wahrscheinlichkeit, daß keine von k = d δ2 e Wiederholungen von 3 und 4 “nein” antwortet, ist also 1 δ 2 δ (1 − )k ≤ (1 − ) δ ≤ exp(−1) ≤ . 2 2 2

Bemerkung: Wiederholt man den Linearit¨ atstest c mal f¨ ur ein gen¨ ugend großes c, so l¨ aßt sich die Wahrscheinlichkeit, daß “nein” ausgegeben wird auf ≥ 1−ε, ε > 0 beliebig klein, erh¨ ohen. Selbstkorrektur Eingabe: x ∈ Fm 2 Ausgabe: Punkt in F2

1. W¨ ahle ein y in Fm allig. 2 zuf¨ 2. Gebe g(x + y) + g(y) aus. m Satz 4. Sei g : Fm 2 → F2 δ-nah an einer linearen Abbildung f : F2 → F2 , 0 < δ < 1/3. Dann gibt Selbstkorrektur mit Wahrscheinlichkeit ≥ 1 − 2δ den Wert f (x) aus.

Beweis:. f, g sind δ-nah. ⇒ Pr[f (y) 6= g(y)] ≤ δ ∧ Pr[f (x + y) 6= g(x + y)] ≤ δ. y

y

⇒ Pr[f (x + y) = g(x + y) ∧ f (y) = g(y)] ≥ 1 − 2δ. y

Wenn f (x + y) = g(x + y) und f (y) = g(y) so folgt aus der Linearit¨ at von f , daß f (x) = f (x + y) + f (y) = g(x + y) + g(y).

24

4 N P ⊂ P CP (N 3 , 1)

Graphen und Algorithmen II

4.3 N P ⊂ P CP (n3 , 1)

ϕ

P CP (n3 , 1)

6  ja/nein π A0

Verifizierer ?

B0

- O(n3 ) zuf.-Bits

C0

Notation 2

F¨ ur x, y ∈ Fn2 sei x ◦ y ∈ Fn2 der Vektor (xi · yj )i,j=1,...,n 2

3

F¨ ur x ∈ Fn2 und y ∈ Fn2 sei x ◦ y ∈ Fn2 der Vektor (xi · yj,k )i,j,k=1...n F¨ ur 3 Funktionen

A0 : Fn2 → F2 2

B 0 : Fn2 → F2 3

C 0 : Fn2 → F2 haben wir den folgenden Konsistenztest Eingabe: A0 , B 0 , C 0 Ausgabe: “ja” oder “nein” 1. Wende den Linearit¨ atstest an auf A0 , B 0 , C 0 (mit Eingabe 1/10) 2. W¨ ahle x, x0 ∈ Fn2 zuf¨ allig.

3. Sei a = Selbstkorrektur(x, A0 ), a0 =Selbstkorrektur(x0 , A0 ) 4. Sei b = Selbstkorrektur(x ◦ x0 , B 0 ) 5. Falls a · a0 6= b0 , antworte “nein”. 2

6. W¨ ahle x ∈ Fn2 , y ∈ Fn2 zuf¨ allig

7. Sei a = Selbstkorrektur(x, A0 ) 8. Sei b = Selbstkorrektur(y, B 0)

9. Sei c = Selbstkorrektur(x ◦ y, C 0 )

10. Falls a · b 6= c, gebe “nein” aus. 11. Gebe “ja” aus.

25

Vorlesung 06.05.04

4 N P ⊂ P CP (N 3 , 1)

Graphen und Algorithmen II

Anmerkung zu 4 und 9: 0

Ba (x ◦ x ) =

n X

i,j=1

xi ·

x0j

· ai · aj = (

n X i=1

xi · ai )(

n X i=1

x0j · aj ) = Aa (x) · Aa (x0 )

Ca (x ◦ y) = Aa (x) · Ba (y)

Der Konsistenztest akzeptiert also bei korrekter Eingabe. Lemma 6. Sei 0 < δ < 1/100. Es gibt eine Zahl k, die nur von δ abh¨angt, so daß folgendes gilt: Angenommen es gibt kein a ˜ ∈ Fn2 , so daß A0 , B 0 , C 0 jeweils δ-nah an Aa˜ , Ba˜ , Ca˜ liegen. Ruft man den Konsistenztest k-mal auf, so ist die Wahrscheinlichkeit, daß die Antwort jedesmal “ja” ist, ≤ δ. ˜ B ˜ sind. Beweis:. Nehme an, daß A0 , B 0 δ-nah an linearen Abbildungen A, ˜ 6= Ba . Betrachte die Abbil⇒ Es gibt ein a ∈ Fn2 , so daß A˜ = Aa . Angenommen B dungsmatrizen MB˜ = (˜bi,j )1≤i,j≤n , MBa = (bi,j )1≤i,j≤n . Dann gibt es eine Zeile, in welcher sich die Matrizen unterscheiden, o.B.d.A. die 1.Zeile. ⇒ Pr[

n X j=1

˜b1j x0 6= j

n X

b1j x0j ] =

j=1

˜ 0 = B a x0 ] ≤ ⇒ Pr[Bx

1 2

1 2

˜ 0 = xt Ba x0 | Bx ˜ 0 6= Ba x0 ] ≤ 1 ⇒ Pr[xt Bx 2 3 ˜ ◦ x0 ) = Ba (x ◦ x0 )] ≤ ⇒ Pr[B(x 4 Satz 5. N P ⊂ P CP (n3 , 1) Beweis:. Der Beweis π wird wiederum interpretiert als Folge von 3 Abbildungen: 2 3 A0 : Fn2 → F2 , B 0 : Fn2 → F2 , C 0 : Fn2 → F2 . Erf¨ ullbarkeitstest 1. F¨ uhre den Konsistenztest f¨ ur A0 , B 0 , C 0 aus und antworte gegebenenfalls “nein”. 2. W¨ ahle r ∈ Fm allig, wobei m = #Klauseln von ϕ. 2 zuf¨ 3. Berechne p˜ = pϕ,r sowie αp˜, qp,1 ˜ , qp,2 ˜ , qp,3 ˜ . 0 4. Sei a = Selbstkorrektur(qp,1 ˜ , A ). 0 5. Sei b = Selbstkorrektur(qp,2 ˜ , B ). 0 6. Sei c = Selbstkorrektur(qp,3 ˜ , C ).

7. Falls αp˜ + a + b + c = 1, gebe “nein” aus, sonst gebe “ja” aus.

26

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

5 N P ⊂ P CP (log n, poly(log n)) 5.1 probabilistisch pr¨ ufbare L¨ osungen Sei Σ ein Alphabet und R ⊂ Σ∗ × Σ∗ eine Relation. Wir interpretieren R wie folgt: R ordnet jeder Probleminstanz x ∈ Σ∗ eine Menge {y ∈ Σ∗ |(x, y) ∈ R} von L¨ osungen zu. Beispiel: x = E3SAT -Instanz; y = alle erf¨ ullenden Belegungen. Definition. R heißt eine P-Relation, falls 1. es ein Polynom f : R → R gibt, so daß |y| ≤ f (|x|) f¨ ur alle y mit (x, y) ∈ R, 2. und auf der Eingabe xty in Polynomzeit entschieden werden kann, ob (x, y) ∈ R.

Seien x, y ∈ Σ∗ , |x| = |y| = n, x = x1 . . . xn , y = y1 . . . yn . Dann sind x, y δ-nah, falls #{i ∈ {1 . . . n}|xi 6= yi } < δ · n.

Definition. Eine Codierung ist eine Funktion E : Σ∗ → Σ∗ mit folgenden Eigenschaften: 1. Sind x, y ∈ Σ∗ von der gleichen L¨ange, so gilt |E(x)| = |E(y)|. 2. Sind x, y ∈ Σ∗ , |x| = |y| und sind E(x), E(y) 1/2-nah, so ist x = y. Im Weiteren gilt stets Σ = {0, 1}. Seien r, q, b : N → N Funktionen. ur eine P-Relation R und eine CodieDefinition. Ein (r, q, b)-L¨osungsverifizierer f¨ rung E ist eine Polynomialzeit-Turingmaschine M mit folgenden Eigenschaften: Seien x, y ∈ Σ∗ , |y| = r(|x|). Dann besteht die Ausgabe von M (x t y) aus 1. einer Folge q1 , . . . , qν von ganzen Zahlen gefolgt von ganzen Zahlen q10 , . . . , qν0 bin¨ar codiert und durch t getrennt. Dabei gilt ν = q(|x|).

2. Einem Schaltnetz C der Gr¨oße poly(q(|x|) + b(|x|)) mit 2νb(|x|) Eing¨angen, so daß folgendes gilt: Vollst¨ andigkeit: Falls (x, z) ∈ R, so gibt es ein π = (π1 . . . π|π| ), πi ∈ {0, 1}b(|x|), so daß gilt: Unterteilt man die Codierung E(z) in Bl¨ocke der L¨ange b(x), indem E(z) = (α1 . . . αn ), |αi | = b(|x|), so gilt C(πq1 , . . . , πqν , αq10 , . . . , αqν0 ) = 1 Korrektheit: Sind x und α = (α1 . . . αn ), |αi | = b(|x|) so, daß f¨ ur ein π = (π1 . . . π|π| ), πi ∈ {0, 1}b(|x|) gilt: Pr[C(πq1 , . . . , πqν , αq10 , . . . , αqν0 ) = 1] ≥ y

1 , 4

so gibt es ein z mit (x, z) ∈ R, so daß α 1/4-nah an E(z) liegt. 27

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

Eingabe x Zufallsbits y R @ Verifizierer Anfragen an π Anfragen an α
A q ...q q10 . . . qν0 ν 
- ? U A 1 C 6 6 b(|x|) Bits b(|x|) Bits ? α L¨ osung ja/nein π Beweis P CS(r, b, q) (“probabilistically checkable solutions”) ist die Menge aller Paare (R, E) wie zuvor, die einen (r, b, q)-L¨ osungsverifizierer zulassen. Beispiel: Sei R = {(ϕ, a)|ϕ ist eine erf¨ ullbare E3SAT -Instanz, a eine erf¨ ullende Belegung von ϕ}. Sei E die Codierung E(a) = Aa , wobei Aa die lineare Abbildung ist, die wir im Abschnitt N P ⊂ P CP (n3 , 1) konstruiert haben. Dann ist (R, E) ∈ P CS(n3 , 1, 1). Der Beweis π besteht aus den linearen Abbildungen (Ba , Ca ). Das n¨ achste Ziel ist zu zeigen, daß R bez¨ uglich einer geeigneten Codierung einen (log n, poly(log n), 1) 3/4-L¨ osungsverifizierer hat.

5.2 Testen von Polynomen niedrigen Grades Um zu testen, ob eine Abbildung g (z.B. gegeben als Wertetabelle) ein Polynom ist, ben¨ otigen wir einige Zusatzinformationen (zus¨ atzlich zur Wertetabelle). Im Folgenden sei k ∈ N, q eine Primzahl. Ferner sei zu d ∈ N: Fd,k = {f ∈ Fq [X1 , . . . , Xk ]|Gradf ≤ d} Sei F = Fq , wir nehmen an, daß d ≤ q/1000. Sei g : Fk → F. Bemerkung: Die Funktion g ist in Fd,k genau dann, wenn f¨ ur alle b, s ∈ Fk gilt, daß die Funktion F → F, t 7→ g(b+t·s) ein Polynom vom Grad ≤ d in einer Variablen ist. Zu b, s ∈ Fk sei Lb,s = {b + t · s|t ∈ F}. Dann ist also Lb,s eine Gerade in Fk ; g ist ein Polynom vom Grad ≤ d genau dann, wenn die Einschr¨ ankung von g auf alle Lq,s ein Polynom vom Grad ≤ d ist. Bemerkung: Dieselbe Gerade kann in verschiedenen Parametrisierungen vorkommen; das heißt es gibt b, s ∈ Fk , β, σ ∈ Fk so daß (b, s) 6= (β, σ), aber Lb,s = Lβ,σ . Aber: Jede Gerade besitzt die gleiche Zahl von Parametrisierungen. Sei nun L = Lb,s eine Gerade. Dann k¨ onnen wir zu jeder Abbildung g : Fk → F ein d d (t) = g(b + t · s)} maximal Polynom PL,g (X) ∈ F1,d ausw¨ ahlen, so daß #{t ∈ F|PL,g 28

Vorlesung 11.05.04

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

wird. Die Auswahl erfolgt konsistent f¨ ur verschiedene Parametrisierungen der Geraden. Die Erfolgsrate von g auf L = Lb,s ist nun: d Pr [PL,g (t) = g(b + t · s)] =

t∈F

d #{t ∈ F|PL,g (t) = g(b + t · s)} . #F

Die Erfolgsrate von g ist: Pr

d [PLb,s,g (t) = g(b + t · s)] = q −2k

b,s∈Fk ,t∈F

X #{t ∈ F|PLdb,s ,g (t) = g(b + t · s]} #F

b,s∈Fk

.

Satz 6. Sei 0 < δ eine gen¨ ugend kleine Zahl. Jede Funktion g : Fk → F, deren δ Erfolgsrate > 1 − 2 ist, ist δ-nah an einem Polynom in Fd,k . Der Beweis des Satzes folgt in Kapitel 8. Der Beweis, daß g : F → F ein Polynom ist, besteht nun aus zwei Teilen: 1. Der Funktion g selbst (als Wertetabelle). 2. Einer Geradentabelle T = Tg . Dies ist die Abbildung T : F2k → Fd+1 . Zu (b, s) ∈ F2k ist T (b, s) also ein Tupel (T (b, s)0 , . . . , T (b, s)d), welches aus den Pd Koeffizienten des Polynoms PLdb,s ,g besteht; d.h. PLdb,s ,g (X) = i=0 T (b, s)i X i . LowDegreeTest Eingabe: δ > 0, g : Fk → F als Wertetabelle, T : F2k → Fd+1 Ausgabe: “ja” oder “nein” 1. Wiederhole das Folgende d δ3 e mal: 2.

W¨ ahle b, s ∈ Fk , t ∈ F zuf¨ allig

3.

Falls das Polynom Pb,s,T (X) :=

d X

T (b, s)i X i

i=0

die Eigenschaft hat, daß Pb,s,T (t) 6= g(b + t · s) gebe “nein” aus. 4. Sonst gebe “ja” aus. Satz 7. Sei 0 < δ eine gen¨ ugend kleine Zahl. Sei g : Fk → F eine Abbildung, q = #F. Dann gilt:

29

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

1. Falls g ∈ Fd,k , so gibt es eine Geradentabelle T = Tg , so daß LowDegreeTest(δ, g, T ) mit Wahrscheinlichkeit 1 akzeptiert. 2. Falls g nicht δ-nah an einem Polynom in Fd,k ist, so antwortet LowDegreeTest(δ, g, T ) f¨ ur jede Tabelle T mit Wahrscheinlichkeit ≥

3 4

“nein”.

3. LowDegreeTest(δ, g, T ) fragt O(1) Werte von g und O(1) Eintr¨age der Tabelle T ab und verwendet O(k log(q)) zuf¨allige Bits. T hat q 2k Eintr¨age der L¨ange O(k log(q)) Beweis:.

1. trivial

2. Sei T die LowDegreeTest vorgelegte Tabelle, sei T ∗ die ideale Tabelle, deren Eintr¨ age die Koeffizienten der Polynome PLb,s ,g sind (b, s ∈ Fk ). Dann gilt: Pr [Pb,s,T (t) = g(b + t · s)] ≤ Pr [Pb,s,T ∗ (t) = g(b + t · s)] =: p∗ .

b,s,t

b,s,t

Falls g nicht δ-nah an einem Polynom ist, dann ist p∗ ≤ 1 − δ2 (s. Satz 6). Also ist die Wahrscheinlichkeit, daß keiner der d δ3 e Versuche auf eine “nein”-Ausgabe f¨ uhrt, beschr¨ ankt durch −3 1 δ 3 δ 3 )< . (1 − ) δ ≤ exp(− · ) = exp( 2 2 δ 2 4 3. trivial

5.3 Codieren mittels Polynomen Sei a = (a1 , . . . , an ) ∈ {0, 1}n ein n-Bit-Wort. Wir wollen ein Polynom fa definieren, welches a codiert. Sei dazu q ≥ 100dlog4 ne eine Primzahl. Sei H = {0, . . . , dlog ne} ⊂ Fq = F. Sei m = d logloglogn n e. Dann ist log n

#H m ≥ log n log log n = n. Wir k¨ onnen daher eine Abbildung fa : H m → {0, 1} derart definieren, daß die Abbildung a 7→ fa injektiv ist. [Sei dazu σ : {1, . . . , n} eine Injektion. Wir definieren fa (σ(i)) := ai , fa (H m \ σ({1, . . . , n}) = 0.] Lemma 7. Es gibt ein Polynom fa0 ∈ F [X1 , . . . , Xm ], so daß fa0 (h) = fa (h) ∀ h ∈ H m und GradXi fa0 ≤ #H ∀ i. Beweis:. Zu jedem x ∈ H gibt es ein ϕx ∈ F [X] mit Gradϕx ≤ #H, so daß  1 falls h = x ϕx (h) = . 0 sonst

30

Vorlesung 13.05.04

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

Definiere nun f¨ ur (x1 , . . . , xm ) ∈ H m das Polynom ϕx1 ,...,xm (X1 , . . . , Xm ) =

m Y

ϕxi (Xi ).

i=1

⇒ GradXi ϕx1 ,...,xm ≤ #H f¨ ur alle i und ϕ h1 , . . . , h m = | {z }



1 falls h = x . 0 sonst

∈H m

Definiere nun fa0 (h) =

X

(x1 ,...,xm )∈H m

fa (x1 , . . . , xm ) · ϕx1 ,...,xm (h).

Lemma 8. Zwei verschiedene Polynome in Fd,k stimmen in h¨ochstens d·q k−1 Punkten von F k ¨ uberein. Sei ϕ eine E3SAT -Formel u ¨ber den booleschen Variablen x1 , . . . , xn . Eine Belegung a von x1 , . . . , xn codieren wir durch das Polynom fa0 . Dieses Polynom fa0 hat Grad md logloglogn n e = d logloglogn n edlog ne. Wir schreiben also fa0 als Wertetabelle auf. Der Platzbedarf daf¨ ur ist O((log log n)q m ) = poly(n). Zus¨ atzlich ben¨ otigt man als Beweis die Geradentabelle T von fa0 . Diese Tabelle hat Gr¨ oße q 2m (d + 1) log q = poly(n). ⇒ Codierung der L¨ osung und Beweis haben L¨ ange poly(n). Mit Hilfe des LowDegoße log q] und von O(1) Tests kann also durch Abfragen von O(1) Werten von fa0 [der Gr¨ Eintr¨ agen von T [je O(m log n log q) = poly(log n) Bits] und mit O(log n) Zufallsbits gepr¨ uft werden, ob fa0 δ-nah an einem Polynom ist.

5.4 Der (erweiterte) LFKN-Test 5.4.1 Testen einer Summe Sei G ein K¨ orper. Ein K¨ orper F , der aus einer Teilmenge der Elemente von G zusammen mit den aus G induzierten Operationen + und × besteht, heißt ein Unterk¨orper von G. Umgekehrt heißt G ein Erweiterungsk¨orper von F . Sei F ein endlicher K¨ orper und G ein Erweiterungsk¨ orper von F . Sei f : F m → G ein Polynom vom Grad ≤ d in jeder Variablen, das Koeffizienten in G hat. Sei H ⊂ F eine Teilmenge. Wir m¨ ochten testen, ob X f (u) = 0. (1) u∈H m

Dazu soll f in nur einem Punkt ausgewertet werden.

31

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

Um einen solchen Test durchzuf¨ uhren, ist eine Tabelle mit zus¨ atzlicher Information erforderlich. Wir betrachten dazu die Abbildungen X f (x1 , . . . , xi , yi+1 , . . . , ym ). gi (x1 , . . . , xi ) = (yi+1 ,...,ym )∈H m−i

Dann gilt gm = f , und gi (x1 , . . . , xi ) =

X

gi+1 (x1 , . . . , xi , y).

(2)

y∈H

Folglich haben wir

X

f (x) =

x∈H m

X

g1 (x1 ).

x1 ∈H

Satz 8. Sei f : F m → G ein Polynom wie zuvor. Es gelte #F ≥ 4md. Sei H ⊂ F . Es gibt eine Prozedur LFKN, die f in einem gleichverteilt zuf¨allig ausgew¨ Pm ahlten Punkt in F m auswertet und dar¨ uber hinaus Zugriff auf eine Tabelle T aus i=1 (d + 1)#F i Eintr¨agen zu je dlog #Ge Bits hat, so daß folgendes gilt. P i. Falls u∈H m f (u) = 0, so gibt es eine Tabelle T = Tf , so daß LFKN mit Wahrscheinlichkeit 1 akzeptiert. P ur jede ii. Falls u∈H m f (u) 6= 0, so lehnt LFKN mit Wahrscheinlichkeit ≥ 34 ab, f¨ Tabelle T . iii. LFKN fragt 1 Punkt von f ab (zuf¨allig gleichverteilt), liest m(d + 1) Eintr¨age aus T und benutzt O(m log #F ) Zufallsbits. Beweis:. Die Prozedur LFKN lautet: 1. W¨ ahle r1 , . . . , rm ∈ F zuf¨ allig. Sei gˆ0 = 0 das Nullpolynom. 2. Interpretiere die Tabelle T als Tabelle von Koeffizienten von Polynomen vom Grad ≤ d (in einer Variablen): zu je i − 1 Elementen x1 , . . . , xi−1 von F enth¨ alt T die Koeffizienten eines Polynoms g˜i (x1 , . . . , xi−1 , X). Lese die Koeffizienten der Polynome gˆi = g˜i (r1 , . . . , ri−1 , X) aus T aus (i = 1, . . . , m). P 3. Falls x∈H gˆi (x) 6= gˆi−1 (ri−1 ), so lehne ab (i = 1, . . . , m).

4. Falls f (r1 , . . . , rm ) 6= gˆm (rm ), so lehne ab, sonst akzeptiere. P ad i.: Falls u∈H m f (u) = 0, so betrachte die oben definierten Polynome gi (X1 , . . . , Xi ) =

X

f (X1 , . . . , Xi , yi+1 , . . . , ym ).

(3)

(yi+1 ,...,ym )

Dann hat gi Grad ≤ d in jeder Variablen. Sind x1 , . . . , xi ∈ F , so erh¨ alt man durch Einsetzen also Polynome gi (x1 , . . . , xi−1 , X) vom Grad ≤ d (in einer Variablen). Die 32

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

Tabelle T = Tf enth¨ alt die Koeffizienten dieser Polynome. Aufgrund von (2) akzeptiert der Test. P ad ii.: Nehme an, daß u∈H m f (u) 6= 0. Sei gi die in (3) definierte Familie von Polynomen. Falls g˜1 = g1 , so ist X X X gˆ1 (x) = f (u) 6= 0, g˜1 (x) = x∈H

u∈H m

x∈H

so daß Schritt 3 mit i = 1 ablehnt. Nehmen wir also an, daß g˜1 6= g1 . Falls dann gˆ2 (r1 , X) = g2 (r1 , X), so ist X gˆ2 (x) = g1 (r1 ). x∈H

Daher f¨ allt der Test, ob g1 (r1 ) =

X

gˆ2 (x) = gˆ1 (r1 )?

x∈H

mit Wahrscheinlichkeit ≥ 1 − d/#F negativ aus, weil die zwei verschiedenen Polynome g1 , gˆ1 in ≤ d Punkten u ¨bereinstimmen. Sei nun allgemeiner i der kleinste Index, so daß gˆi = gi (r1 , . . . , ri−1 , X) (1 ≤ i ≤ m). Dann gilt X gi−1 (ri−1 ) = gˆi (r1 , . . . , ri−1 , x), x∈H

und wegen gi−1 6= gˆi−1 ist die Wahrscheinlichkeit, daß LFKN ablehnt (in Schritt 3), ≥ 1 − d/#F . Falls gˆi 6= gi (r1 , . . . , ri−1 , X) f¨ ur alle i, so ist gˆm 6= gm (r1 , . . . , rm−1 , X). Weil f (r1 , . . . , rm−1 , X) = gm (r1 , . . . , rm−1 , X) ein Polynom vom Grad ≤ d ist, folgt, daß Schritt 4 mit Wahrscheinlichkeit ≥ 1 − d/#F ablehnt. Da wir d/#F < 1/4 angenommen haben, leht also LFKN mit Wahrscheinlichkeit ≥ 34 ab. ad iii.: Um m Elemente aus F zuf¨ allig auszuw¨ ahlen, werden m log #F Zufallsbits ben¨ otigt. Insgesamt sind ≤ m(d + 1) Anfragen an T erforderlich. 5.4.2 Der erweiterte LFKN-Test Sei f : F m → F ein Polynom vom Grad ≤ d in jeder Variablen. Wir m¨ ochten testen, ob f¨ ur eine gegebene Menge H ⊂ F gilt f (u) = 0 f¨ ur all u ∈ H m . Satz 9. Sei f : F m → F ein Polynom vom Grad ≤ d in jeder Variablen. Sei F ein endlicher K¨orper von Primzahlordnung und H ⊂ F . Es gelte #F ≥ 4m(d + #H). Es gibt eine Prozedur XLFKN, die Zugriff auf f und eine Tabelle T aus O(d#F 2m ) Eintr¨agen zu je d(m + 1) log #F e Bits hat, so daß folgendes gilt: 1. Falls f (u) = 0 f¨ ur alle u ∈ H m , so gibt es eine Tabelle T = Tf , so daß XLFKN mit Wahrscheinlichkeit 1 akzeptiert.

33

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

2. Falls f (u) 6= 0 f¨ ur ein u ∈ H m , so lehnt XLFKN f¨ ur jede Tabelle T mit Wahrscheinlichkeit ≥ 34 ab. 3. XLFKN fragt f an 5 gleichverteilt und unabh¨angig zuf¨allig gew¨ahlten Punkten von F m ab, liest O(md) Eintr¨age von T und verwendet O(m log #F ) Zufallsbits. Beweis:. Sei K ein Erweiterungsk¨ orper von F , so daß 2#H m ≤ #K ≤ 2#H m #F ; ein solcher K¨ orper existiert stets (s. [9] f¨ ur einen Beweis). Sei ρ : H → {0, 1, . . . , #H − 1} eine Bijektion. Zu u = (u0 , . . . , um−1 ) ∈ H m definieren wir σ(u) =

m−1 X

ρ(ui )#H i .

i=0

Dann ist σ : H m → {0, 1, . . . , #H m − 1} ⊂ Z eine Bijektion (wobei wir den Ausdruck auf der rechten Seite von σ(u) als Ausdruck u ¨ber Z interpretieren, nicht u ¨ber K). Wir definieren nun eine Funktion g : K → K durch X f (u)tσ(u) . g : t 7→ u∈H m

Dann ist g ein Polynom vom Grad ≤ #H m . Es gilt also entweder f (u) = 0 f¨ ur alle u ∈ H m (also g = 0) oder g hat ≤ #H m Nullstellen. Da #K ≥ 2#H m , folgt also (∃u ∈ H m : f (u) 6= 0) → Pr (g(t) = 0) ≤ t∈K

1 . 2

Wir m¨ ochten nun den LFKN-Test verwenden, um zu testen, ob g(t) = 0 f¨ ur ein zuf¨ alliges t ∈ K. Dazu zeigen wir zun¨ achst, daß f (u)tσ(u) f¨ ur jedes t ein Polynom in u (mit Koeffizienten in K) ist; denn f¨ ur alle u ∈ H m gilt f (u)tσ(u)

= f (u)

m−1 Y

t#H

i

ρ(ui )

= f (u)

i=0

m−1 Y

(

X

t#H

i

ρ(h)

Lh (ui )),

i=0 h∈H

wobei Lh das Polynom vom Grad ≤ #H mit der Eigenschaft  1 falls x = h Lh (x) = 0 falls x ∈ H \ {h} ist. Also ist f (u)tσ(u) ein Polynom vom Grad ≤ d + #H in jeder Variablen ui (bzw. kann durch ein solches Polynom auf F m fortgesetzt werden). Ein Wert dieses Polynoms kann durch Abfrage eines Wertes von f ermittelt werden. Nun k¨ onnen wir X 0 = g(t) = f (u)tσ(u) u∈H m

testen. Die Annahmen des LFKN-Tests sind erf¨ ullt, so daß im Fall g(t) 6= 0 LFKN dies mit Wahrscheinlichkeit ≥ 34 feststellt. Falls nun g(t) 6= 0 f¨ ur ein t ∈ K, so ist die Wahrscheinlichkeit, daß g(t1 ) = · · · = g(t5 ) = 0 34

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

f¨ ur 5 zuf¨ allig gew¨ ahlte Punkte ≤ 1/32 (weil g ja h¨ ochstens #H m Nullstellen hat). Die Wahrscheinlichkeit, daß in ti also g(ti ) = 0 gilt oder der LFKN-Test versagt, ist ≤ 12 + 14 = 34 . Mit Wahrscheinlichkeit ( 34 )5 < 41 lehnt der soeben beschriebene Test also nicht ab. Die Wahrscheinlichkeit, daß g 6= 0 festgestellt wird, ist also ≥ 3/4. Die Tabelle T f¨ ur XLFKN enth¨ alt die LFKN-Tabellen f¨ ur alle Funktionen u 7→ f (u)tσ(u) , m mit t ∈ K. Weil #K ≤ 2#H #F , hat T daher ≤ 2#H m #F m(d + 1)#F m−1 = O(d#F 2m ) Eintr¨ age zu je O((m+1) log #F ) Bits. Der XLFKN-Test ben¨ otigt insgesamt O(m log #F ) Zufallsbits und liest insgesamt O(m(d + #H)) Eintr¨ age aus T .

5.5 N P ⊂ P CP (log n, poly(log n))

Sei ϕ = C1 ∧ . . . ∧ Cn eine E3SAT -Instanz in n Variablen. Sei Cˆi das zu Ci geh¨ orende Polynom aus I mit Koeffizienten in Z. Sei Cˆ = (Cˆ1 , . . . , Cˆn ). Jedes der Polynome Cˆi ist von einem der folgenden 4 Typen: 1. P1 (X, Y, Z) = XY Z 2. P2 (X, Y, Z) = XY (1 − Z) 3. P3 (X, Y, Z) = X(1 − Y )(1 − Z) 4. P4 (X, Y, Z) = (1 − X)(1 − Y )(1 − Z) Mit Cj wird nun die Menge der Klauseln unter C1 , . . . , Cn bezeichnet, so daß Cˆi vom Typ j ist. Sei V die Menge der booleschen Variablen in ϕ und sei W : V → {0, 1} eine Belegung. Falls W eine erf¨ ullende Belegung ist und Cˆi = Pj (X, Y, Z), so gilt Pj (W (X), W (Y ), W (Z)) = 0. Falls dies umgekehrt f¨ ur alle Klauseln Ci gilt, so ist W eine erf¨ ullende Belegung. Sei χj : V 3 → {0, 1} mit  1 falls es in Cj eine Klausel mit den Variablen X, Y, Z gibt χj (X, Y, Z) = . 0 sonst

Die so festgelegten Punkte von χj k¨ onnen zu einem Polynom fortgesetzt werden. F¨ ur jede Belegung W : V → {0, 1} gilt nun: W erf¨ ullt ϕ gdw. f¨ ur j = 1, . . . , 4 gilt: χj (X, Y, Z)Pj (X, Y, Z) = 0 ∀ (X, Y, Z) ∈ V 3 . Wir konstruieren mit Hilfe des LFKN-Tests nun einen L¨ osungsverifizierer f¨ ur E3SAT bez¨ uglich einer geeigneten Codierung. Sei ϕ = C1 ∧. . . ∧Cn eine E3SAT -Instanz mit n Variablen V . Sei p die kleinste Primzahl ≥ log5 n [p kann in Polynomzeit(n) berechnet werden und ist O(log5 n)]. Sei F = Fp , H ⊂ F , #H = dlog ne. Sei m = d logloglogn n e. ⇒ #H m ≥ n. o.B.d.A. gelte #H m = #V = n. Dann gibt es eine Bijektion H m ↔ V. Wir identifizieren H m und V (H m = V ). D.h. die Belegung W : V → {0, 1} ist eine Abbildung W : H m → {0, 1}, χj : V 3 = H 3m → {0, 1}. Wie vorher gezeigt gibt es

35

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

Polynome W 0 und χ0j vom Grad ≤ #H 3 in jeder Variablen, so daß W und W 0 bzw. χj und χ0j auf H m bzw. H 3m u ¨bereinstimmen. Sei fj (X, Y, Z) = χ0j (X, Y, Z)Pj (W 0 (X), W 0 (Y ), W 0 (Z)), X, Y, Z ∈ F m . ⇒ fj ∈ F [X1 , . . . , Xm , Y1 , . . . , Ym , Z1 , . . . , Zm ] ist ein Polynom in 3m Variablen vom Grad poly(log n). Die Codierung der Belegung W ist nun einfach die Wertetabelle von W 0 . Der Beweis lautet π = AB1 B2 B3 B4 , wobei A die Geradentabelle von W 0 f¨ ur LowDegreeTest ist, Bj die Tabelle f¨ ur den LFKN-Test von fj ist. Diese Codierung wird mit E1 bezeichnet.

Vorlesung 18.05.04

Satz 10. (RE3SAT , E1 ) ∈ P CS(log n, poly(log n), poly(log n)) Beweis:. Wir konstruieren einen entsprechenden Verifizierer. Der Verifizierer berechnet aus der Eingabe ϕ zun¨ achst die Primzahl p, die Menge H und die Polynome χj : F3m → F. Der Verifizierer interpretiert die vorgelegte L¨ osung als Abbildung ˜ : F → F. Den Beweis π interpretiert er als π = A˜B ˜1 B ˜2 B ˜3 B ˜4 , wobei W ˜ sein soll. A˜ die Tabelle f¨ ur den LowDegreeTest f¨ ur W ˜i Tabellen f¨ B ur den LFKN-Test sein sollen. Der Verifizierer hat zu pr¨ ufen, ob ˜ vom Grad ≤ #H in jeder Variable ist und ˜ δ-nah an einem Polynom W ˜ 1. W ˜ ˜ ˜ ˜ (x), W ˜ (y), W ˜ (z)) = 0. 2. f¨ ur alle (x, y, z) ∈ V 3 = H 3m gilt: χj (x, y, z)Pj (W

3

Das tut er folgendermaßen: ˜ und A. ˜ 1. F¨ uhre den LowDegreeTest durch. Dieser liest von W ˜ ist das Polynom wie in 1. Sei ˜ 2. Angenommen W ˜ ˜ ˜ ˜ ˜ (x), W ˜ (y), W ˜ (z)). f˜j (x, y, z) = χj (x, y, z) · Pj (W ˜ Um zu testen, ob f˜j (H 3m ) = 0, j = 1, . . . , 4, f¨ uhren wir den LFKN-Test mit der ˜ ˜j durch. Dieser fragt 5 zuf¨ Tabelle B allig unabh¨ angig gew¨ ahlte Punkte aus F2m ˜ von f˜ ab. Diese Anfragen werden vom Verifizierer beantwortet, indem dieser χ j

j

˜ berechnet. und W Falls das δ in 1. klein genug gew¨ ahlt ist, stimmen die so erhaltenen Werte mit 3 Notation:

statt χ0j schreiben wir im folgenden kurz χj .

36

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

˜ Wahrscheinlichkeit ≥ 9/10 mit den Werten von f˜ u ¨berein. In diesem Fall akzep˜ tiert LFKN mit Wahrscheinlichkeit ≤ 1/2, falls f˜(H 3m ) 6= 0. Wiederholt man c mal (c ist eine gen¨ ugend große Konstante), so ergibt sich eine Gesamtfehlerwahrscheinlichkeit < 1/4. Andererseits akzeptiert der Verifizierer in der idealen Situation mit Wahrscheinlichkeit 1. Ressourcen: ˜ (=L¨ LowDegreeTest: O(1) Werte von W osung) der L¨ ange O(log p) und O(1) Werte der L¨ ange poly(log n) von A˜ (d.h. vom Beweis), O(m log p) = O(log n) Zufallsbits.

LFKN: (m#H 3 ) = poly(log n) Eintr¨ age der L¨ ange O(m log #F ) = O(log n) ˜j ’s, O(1) Werte der L¨ ˜ , O(m log p) = O(log n) der B ange poly(log n) von W Zufallsbits.

Korollar 1. P CP (log n, poly(log n)) = N P Bemerkung: Der oben konstruierte Verifizierer liest nur O(1) Bl¨ ocke der L¨ ange poly(log n) aus der L¨ osung, aber poly(log n) viele Bl¨ ocke aus dem Beweis.

5.6 (RE3SAT , E1 ) ∈ P CS(log n, poly(log n), 1) α

poly(log n) Y HH  * HH  poly O(1) Verifizierer n) H(log  H  H   j H

π A B1 B2 B3 B4

besteht aus Bl¨ ocken der Gr¨ oße poly(log n)

Wir modifizieren den Beweis und den Verifizierer aus dem letzten Abschnitt 5.5 so, daß nur O(1) aufeinander folgende Sequenzen in dem Beweis gelesen werden. F¨ ur die L¨ osung trifft dies bereits zu. Idee: Wir konstruieren einen neuen Beweis, in dem alle m¨ oglichen Anfragen des alten Verifizierers als aufeinanderfolgende Sequenzen enthalten sind. Satz 11. Sei E1 die Codierung aus dem Abschnitt 5.5. Dann gilt, daß (RE3SAT , E1 ) ∈ P CS( log n , poly(log n) , |{z} 1 ) | {z } | {z } ocke Zufallsbits L¨ ange der Bl¨ ocke # Bl¨

Beweis:. Sei V der Verifizierer aus dem Abschnitt 5.5. Der Beweis, den V erwartet hat L¨ ange L = poly(n). Sei r die kleinste Primzahl > log2 L · logc n, wobei c eine gen¨ ugend

37

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

große Konstante ist. Sei m = d logloglogLL e. Sei G = Fr , I = {0, 1, . . . , log L} ⊂ G. Wie im Abschnitt 5.5 fassen wir nun den Beweis π des alten Verifizierers als Abbildung π : I m → {0, 1} auf. Dann k¨ onnen wir π zu einem Polynom π 0 : Gm → G fortsetzen, welches Grad ≤ #I in jeder Variablen hat. Sei q(n) die Zahl der Anfragen, die V an den Beweis π stellt. Zu a0 , . . . , aq(n) ∈ Gm bezeichnen wir mit Pa0 ...aq(n) : G → Gm das Polynom, welches die Eigenschaft Pa0 ...aq(n) (j) = aj , (j = 0, . . . , q(n)) hat, wobei sein Grad ≤ q(n) ist. Genauer: Die m Komponenten (Pa0 ...aq(n) )i mit i = 1, . . . , m sind Polynome G → G mit Grad ≤ q(n), so daß (Pa0 ...aq(n) )i {z } |

(j) =

aji |{z}

.

i−te Komponente von aj

i−te Komponente von jedem Wert

Die L¨ osung f¨ ur unseren neuen Verifizierer V˜ ist genau die L¨ osung f¨ ur den alten Verifizierer V . Aber der neue Verifizierer V˜ interpretiert seinen Beweis π ˜ anders. π ˜ wird interpretiert als Konkatenation von 1. Der Wertetabelle des Polynoms π 0 (das enth¨ alt insbesondere den alten Beweis). 2. Der Tabelle f¨ ur den LowDegreeTest von π 0 , T˜. 3. Die Koeffizienten der Polynome π 0 (Pa0 ...aq(n) (X)) f¨ ur alle Tupel (a1 , . . . , aq(n) ), die bei Eingabe ϕ als Bitadressen von dem alten Verifizierer V f¨ ur irgendeinen Zufallsstring τ abgefragt werden k¨ onnten, und alle a0 ∈ Gm . Genau so s¨ ahe also der ideale Beweis aus. interpretiert als:

4

Der real gegebene Beweis wird von V˜

1. eine Wertetabelle π ˜ 0 gefolgt von 2. einer Tabelle T˜ gefolgt von 3. Koeffizienten von Polynomen ha0 ...aq (a0 , . . . , aq ) wie zuvor.

4 Anmerkung:

Die Zahl der m¨ oglichen τ ’s ist poly(n).

38

Vorlesung 25.05.04

5 N P ⊂ P CP (LOG N, POLY(LOG N ))

Graphen und Algorithmen II

V˜ geht wie folgt vor: 1. Wende den LowDegreeTest auf π ˜ 0 , T˜ an, um zu testen, ob π ˜ 0 δ-nah an einem ˜ Polynom π ˜ liegt, wobei δ hinreichend klein ist. 2. Bestimme die Positionen a1 , . . . , aq , die der alte Verifizierer V von seinem Beweis gelesen h¨ atte. 3. W¨ ahle a0 ∈ Gm zuf¨ allig und berechne (selbst) Pa0 ...aq . 4. Frage die Koeffizienten des Polynoms P = ha0 ...aq ab. Vermeintlich ist dies π 0 ◦ Pa0 ...aq . 5. Teste, ob V den Beweis P (1) . . . P (q) akzeptieren w¨ urde. 6. W¨ ahle t ∈ G zuf¨ allig und pr¨ ufe, ob P (t) = π ˜ (Pa0 ...aq (t)). Falls dies gilt, akzeptiere, sonst lehne ab. ˜ die L¨ Sei ϕ die Eingabe (E3SAT -Instanz). Sei W osung, die V˜ vorgelegt wird. Falls ˜ W eine erf¨ ullende Belegung codiert und π die ideale Form hat, so akzeptiert V˜ mit Wahrscheinlichkeit 1. Angenommen, dies ist nicht der Fall, dann akzeptiert V einen beliebigen Beweis π mit Wahrscheinlichkeit ≤ 1/4. Daher gen¨ ugt es zu zeigen, daß V˜ mit Wahrscheinlichkeit ≥ 1/2 feststellt, wenn die Werte P (1), . . . , P (q) “falsch” sind, d.h. nicht mit π 0 (aj ), j = 1, . . . , q u ¨bereinstimmen. Was ist nun die Wahrscheinlichkeit, daß Schritt 6 es ˜ nicht feststellt, wenn die Polynome P und π ˜ (Pa1 ...aq ) verschieden sind? F¨ ur jedes t ist der Punkt Pa0 ...aq (t) gleichverteilt, wenn a0 zuf¨ allig gew¨ ahlt ist. Ferner gilt mit Wahrscheinlichkeit 1 − δ ˜ π ˜ 0 (Pa0 ...aq (t)) = π ˜ (Pa0 ...aq (t)). P ist, da durch seine Koeffizienten bestimmt, ein Polynom vom Grad ≤ q · m · #I. ˜ Nach Konstruktion ist ebenso π ˜ ◦ Pa0 ...aq ein Polynom in einer Variablen vom Grad ≤ q · m · #I. Weil t im Schritt 6 zuf¨ allig gew¨ ahlt ist und wir angenommen haben, daß ˜ P 6= π ˜ ◦ Pa0 ...aq , folgt Pr[˜ π 0 (Pa0 ...aq (t)) 6= P (t)] ≥ 1 − δ − (w¨ ahle r = #G hinreichend groß)

39

3 q · m#I ≥ #G 4

6 KOMPOSITION DER VERIFIZIERER

Graphen und Algorithmen II

Ressourcen: LowDegreeTest in Schritt 1 braucht O(1) Anfragen an π ˜ 0 der L¨ ange O(log n) ˜ und O(1) Anfragen an T der L¨ ange O(m · #I · log r) = poly(log n). LowDegreeTest braucht O(log n) Zufallsbits. Um a0 zu w¨ ahlen werden O(m · log r) = O(log n) Zufallsbits ben¨ otigt. Koeffizienten von P : Eine Abfrage der L¨ ange O(q · log r) = poly(log n) t ∈ G w¨ ahlen: O(log r) = O(log n) Zufallsbits. f¨ ur 6: O(1) Abfragen an den Beweis zu je log(r) = O(log n) Bits. V fragt O(1) Bl¨ ocke der L¨ osung ab und braucht O(log n) Zufallsbits.

6 Komposition der Verifizierer Fahrplan: 1. N P ⊂ P CP (n3 , 1, 1) 2. N P ⊂ P CP (log n, poly(log n), 1) liegen als bisherige Ergebnisse vor. Daraus folgern wir nun: 3. N P ⊂ P CP (log n, poly(log log n)) Aus 1. und 3. geht dann hervor: 4. N P ⊂ P CP (log n, 1) Lemma 9. Sei RE3SAT die P-Relation, welche aus allen Paaren (ϕ, a) besteht, so daß ϕ eine E3SAT -Formel ist und a eine erf¨ ullende Belegung von ϕ. Sei E die Codierung, die einer Belegung a ∈ {0, 1}∗ als Codewort die Wertetabelle der linearen Abbildung Aa zuordnet. Dann ist (RE3SAT , E) ∈ P CS(n3 , 1, 1). Beweis:. Zun¨ achst einmal ist E eine Codierung. Denn, falls a 6= a0 ⊂ {0, 1}n, Pr( x

n X i=1

a i xi =

n X

a0i xi ) =

i=1

1 . 2

Damit sind E(a) und E(a0 ) nicht weniger als 12 -nah. Betrachte Ba Ca als Beweis. Der L¨ osungsverifizierer f¨ ur (RE3SAT , E) ∈ P CS(n3 , 1, 1) funktioniert nun genauso wie der Verifizierer von E3SAT ∈ P CP (n3 , 1, 1)

40

6 KOMPOSITION DER VERIFIZIERER

Graphen und Algorithmen II

6.1 Aufspalten der L¨ osungscodierung Bisher haben wir 2 Codierungen: E0 : Codierung als lineare Abbildung E1 : Codierung mittels Polynomen Sei nun E : Σ∗ → Σ∗ eine Codierung und d ∈ N. Sei y ∈ Σ∗ so, daß d||y|. Dann k¨ onnen wir eine neue Codierung E 0 definieren durch E 0 : y 7→ (E(y1 ) . . . E(yd )) wobei y = y1 . . . yd , |y1 | = |y2 | = . . . = |yd |. Falls d - |y|, h¨ angen wir Nullen an y an. Lemma 10. Sei d ∈ N. Sei E00 die zu E0 wie oben konstruierte Codierung. Dann gilt: (RE3SAT , E00 ) ∈ P CS(n3 , 1, 1) ∀ d ∈ N (RE3SAT , E00 ).

3

Beweis:. Sei V0 der “alte” P CS(n , 1, 1)-Verifizierer f¨ ur Sei ϕ die Eingabe (E3SAT -Instanz). ϕ habe n Variablen und n Klauseln. Wir konstruieren einen neuen Verifizierer V00 f¨ ur (RE3SAT , E00 ). V00 interpretiert seine L¨ osung s als Wort s1 . . . sd , n/d wobei si : F2 → F2 als Wertetabelle aufgefaßt wird. V00 interpretiert seinen Beweis π 0 als π 0 = eπ, wobei π der Beweis des alten Verifizierers V0 , und e die Wertetabelle einer Abbildung Fn2 → F2 ist. V00 wendet den alten Verifizierer auf e als L¨ osung und auf den Beweis π an, um zu pr¨ ufen, ob e = E0 (y 0 ) f¨ ur eine erf¨ ullende Belegung y 0 von φ. Falls V0 ablehnt, lehnt auch V00 ab. Zu pr¨ ufen ist nun, ob in der Tat si = E0 (yi0 ) 0 0 0 0 f¨ ur i = 1, . . . , d, wobei y = y1 . . . yd , |y1 | = . . . = |yd0 |. Zun¨ achst pr¨ uft V00 mittels Lin/d nearit¨ atstest, ob s δ-nah an der Wertetabelle einer linearen Abbildung s˜i : F2 → F2 liegt. Dann wird die folgende Prozedur verwendet, um zu pr¨ ufen, ob s˜i = E0 (yi0 ) ∀ i. n/d

Konsistenztest W¨ ahle w1 . . . wd ∈ F2 zuf¨ allig unabh¨ angig. Sei w ∈ Fn2 der Vektor w = (w1 . . . wd ) Falls e(w) 6= s1 (w1 ) + . . . + sd (wd ), gebe “nein” aus, sonst gebe “ja” aus. Falls die L¨ osung und der Beweis die ideale Form haben, so akzeptiert der Konsistenztest mit Wahrscheinlichkeit 1, also akzeptiert V00 mit Wahrscheinlichkeit 1. Nehme nun umgekehrt an, daß eine gen¨ ugend große, aber konstante Zahl von Wiederholungen obiger Tests stets akzeptiert hat. Dann ist mit Wahrscheinlichkeit 1 − ε n/d jedes si ε2 -nah an einer linearen Abbilding s˜i : F2 → F2 , d.h. s˜i = E0 (yi ) f¨ ur ein n/d yi ∈ {0, 1} ’. Setze y = (y1 . . . yd ) ∈ {0, 1}d. Falls y 6= y 0 , so gilt f¨ ur ein zuf¨ alliges ω ∈ Fn2 , daß Pr( ω

n X i=1

yi ωi 6=

n X i=1

yi0 ωi ) ≥ 1/2.

41

Vorlesung 27.05.04

6 KOMPOSITION DER VERIFIZIERER

Graphen und Algorithmen II

Wiederholt man den Konsistenztest also x mal, so ist die Wahrscheinlichkeit, daß f¨ alschlicherweise jedesmal akzeptiert wird ≤ (1/2 + d · ε2 + 1/4)x + d · ε1 < 1/10 (wenn x, ε1 , ε2 geeignet). Sei nun E1 die Codierung mittels Polynomen und E10 die d-te Aufspaltung dieser Codierung. Satz 12. F¨ ur jedes d ∈ N gilt: (RE3SAT , E10 ) ∈ P CS(log n, poly(log n), 1). Beweis:. Sei ϕ eine E3SAT -Instanz mit n Variablen und n Klauseln. Eine Belegung a ∈ {0, 1}n von ϕ wird als Abbildung a : H m → {0, 1} aufgefaßt, wobei H ⊂ Fp , p geeignet. Diese Abbildung a wird zu einem Polynom Fm p → Fp fortgesetzt. Wir nehmen nun an, daß #H m−1 = n/d. Sei H = {0 . . . h}. Sei F = Fp und χj das Polynom  1 falls j = x χj (x) = 0 falls x ∈ H \ {h} f¨ ur x ∈ H mit Gradχj ≤ #H. Sei a = a1 . . . ad die Aufteilung von a in d gleich lange W¨ orter. Dann kann jedes ai als Abbildung ai : H m−1 → {0, 1} aufgefaßt und zu einem Polynom a0i : Fm−1 → F m¨ oglichst kleinen Grades fortgesetzt werden. Das Polynom a0i : Fm → F hat die Eigenschaft, daß a0i (x, y) =

d X

χj (x)aj (y)

i=1

mit x ∈ F, y ∈ Fm−1 . Die Codierung E10 (a) ergibt die Konkatenation der Wertetabellen von a1 , . . . , ad . Sei V1 der alte Verifizierer aus Kapitel 4. Wir konstruieren jetzt einen neuen Verifizierer V10 . Dieser interpretiert seine L¨ osung als Konkatenation s1 . . . sd , wobei si : Fm−1 → F. Der Beweis wird interpretiert als π = (e, π 0 , π1 , . . . , πd ), wobei e als Codierung E1 (a) aufgefaßt wird, π 0 der Beweis f¨ ur V1 sein soll, daß e eine E1 -codierte L¨ osung der Instanz ϕ ist, π1 . . . πd die Tabellen f¨ ur den LowDegreeTest von s1 . . . sd sein sollen. V1 wendet zun¨ achst den alten Verifizierer an auf die L¨ osung e und den Beweis π 0 ; 0 falls dieser ablehnt, lehnt auch V1 ab. Wir gehen im Fall, daß V10 akzeptiert, davon aus, daß e 1/4-nah an einer L¨ osung E1 (a) liegt. Zu pr¨ ufen ist, ob E10 (a) = (s1 . . . sd ). 0 Zun¨ achst wendet V1 den LowDegreeTest auf (s1 , π1 ), . . . , (sd , πd ) hinreichend h¨ aufig an. Im Akzeptanzfall sind also s1 , . . . , sd δ-nah an Polynomen s˜1 , . . . , s˜d . Dann wendet der Verifizierer V10 folgende Routine hinreichend oft an:

42

6 KOMPOSITION DER VERIFIZIERER

Graphen und Algorithmen II

Konsistenztest: W¨ ahle x ∈ F und y ∈ Fm−1 zuf¨ allig unabh¨ angig und pr¨ ufe, ob e(x, y) =

d X

χj (x)sj (y)

j=1

Die Polynome χj kann der Verifizierer dabei selbst berechnen. Falls L¨ osung und Beweis die ideale Gestalt haben, so ist klar, daß V10 mit Wahrscheinlichkeit 1 akzeptiert. Falls dies nicht der Fall ist, aber V10 akzeptiert, so ist mit Wahrscheinlichkeit 1 − ε si δ-nah an einem Polynom s˜i , i = 1, . . . , d. Dann ist die Wahrscheinlichkeit, daß nach k Wiederholungen der Konsistenztest f¨ alschlicherweise akzeptiert, ≤(

l 1 1 + d · δ + )k + d · ε < #Fm 4 4 p

f¨ ur δ, k, ε geeignet gew¨ ahlt, wobei l = max(Grade, Grad

Pd

j=1

χj s j )

6.2 Kompositionslemma Lemma 11. Seien r1 , r2 , b1 , b2 : N → N. Angenommen es gilt folgendes 1. E3SAT ∈ P CP (r1 , b1 , 1). 2. Es gibt eine Codierung E, so daß f¨ ur jedes (von der Eingabe unabh¨angige) d ∈ N gilt: Die d0 te Aufspaltung E 0 von E hat die Eigenschaft, daß (RE3SAT , E 0 ) ∈ P CS(r2 , b2 , 1). Dann gilt: E3SAT ∈ P CP (r1 + r2 (poly(b1 )), b2 (poly(b1 )), 1). Beweis:. Sei V1 ein P CP (r1 , b1 , 1)-Verifizierer f¨ ur E3SAT, der stets r1 (n) Zufallsbits verwendet und d1 = O(1) Bl¨ ocke der L¨ ange b1 (n) aus seinem Beweis liest. Der Beweis π f¨ ur V1 bestehe aus ν = ν(n) Bl¨ ocken der Gr¨ oße b1 (n) : π = (π1 , . . . , πν ). Sei ϕ eine E3SAT -Instanz mit n Variablen und n Klauseln. F¨ ur jeden Zufallsstring τ ∈ {0, 1}r1 konstruiert V1 ein Schaltnetz Φ(ϕ, τ ), das b1 · d1 Eing¨ ange hat. Die Antwort von V1 auf Eingabe ϕ bei Zufallsstring τ ist der Wert des Schaltnetzes Φ(ϕ, τ ), wenn man an die Eing¨ ange die Bl¨ ocke πq1 , . . . , πqd anlegt, wobei q1 , . . . , qd von V1 mittels ϕ und τ berechnet werden. Zu dem Schaltnetz Φ(ϕ, τ ) k¨ onnen wir in Polynomzeit eine E3SAT -Formel Fϕ,τ konstruieren, in der die Variablen(bl¨ ocke) πq1 , . . . , πqd vorkommen, sowie ein weiterer Block z aus poly(b1 ) Variablen, so daß gilt: ∃ Belegung von z : Fϕ,τ (πq1 , . . . , πqd , z) = 1 ⇔ Φ(ϕ, τ )[πq1 , . . . , πqd ] = 1. (o.B.d.A. bestehe z aus genau b1 Variablen.) Wir konstruieren nun den gesuchten Verifizierer V : V soll ein P CP (r1 + r2 (poly(b1 )), b2 (poly(b1 )), 1)-Verifizierer sein.

43

Vorlesung 01.06.04

6 KOMPOSITION DER VERIFIZIERER

Graphen und Algorithmen II

V interpretiert seinen Beweis als Zusammensetzung (e1 , . . . , eν(n) , (fτ , ρτ )τ ∈{0,1}r1 ) mit n = # Variablen = # Klauseln in der Eingabeformel ϕ. V w¨ ahlt einen Zufallsstring τ ∈ {0, 1}r1 und konstruiert die Formel Fϕ,τ . Anschließend berechnet V die Positionen q1 , . . . , qd , die V1 von seinem Beweis bei Eingabe ϕ und Zufallsstring τ abgefragt h¨ atte. Schließlich simuliert V den L¨ osungsverifizierer V2 auf Eingabe Fϕ,τ mit der L¨ osung (eq1 , . . . , eqd , fτ ), Beweis ρτ und Zufallsstring τ 0 ∈ {0, 1}r2(#Fϕ,τ ) . (#Fϕ,τ = # Klauseln in Fϕ,τ = poly(b1 )) Der Zufallsstring f¨ ur V ist (τ, τ 0 ). V akzeptiert genau dann, wenn V2 akzeptiert. Angenommen ϕ ist erf¨ ullbar. z.z.: Es existiert Beweis π V = (e1 , . . . , eν(n) , (fτ , ρτ )τ ∈{0,1}r1 ), so daß V mit Wahrscheinlichkeit 1 akzeptiert. Denn: Es gibt einen Beweis π = (π1 , . . . , πν ) mit πi ∈ {0, 1}b1(n) , so daß V1 f¨ ur jeden Zufallsstring τ akzeptiert. Folglich gilt f¨ ur jedes τ, daß Φ(ϕ, τ )[πq1 , . . . , πqd1 ] = 1, wobei qi = qi (ϕ, τ ) die Anfragen sind, die V1 auf Eingabe ϕ bei Zufallsstring τ stellt. Also gibt es stets ein z(ϕ, τ ) ∈ {0, 1}b1 , so daß Fϕ,τ (πq1 , . . . , πqd1 , z(ϕ, τ )) = 1. Setze also ei = E(πi ) mit i = 1, . . . , ν, fτ = E(z(ϕ, τ )) mit τ ∈ {0, 1}r1 . Zu jedem τ gibt es dann einen Beweis ρτ , so daß V2 die L¨ osung (eq1 , . . . , eqd1 , fτ ) = (E(πq1 ), . . . , E(πqd1 ), E(z, ϕ, τ )) = E 0 (πq1 , . . . , πqd1 , z(ϕ, τ )) akzeptiert, f¨ ur jeden Zufallsstring τ 0 . Also akzeptiert V den soeben konstruierten Beweis mit Wahrscheinlichkeit 1. Umgekehrt ist zu zeigen: Ist π V = (e1 , . . . , eν , (fτ , ρτ )τ ) ein Beweis, so daß p∗ := Pr0 [V akzeptiert die Eingabe ϕ und den Beweis π V ] > τ,τ

1 2

⇒ ϕ ist erf¨ ullbar. Denn: Wir verwenden π V , um einen Beweis π 0 zu konstruieren, so daß 1 Pr[V1 akzeptiert ϕ bei Beweis π 0 ] > . τ 4 Aus der Korrektheit von V1 folgt dann, daß ϕ erf¨ ullbar ist. Sei E −1 die zu E inverse ∗ Kodierung, d.h. zu einem Wort w ∈ {0, 1} ist E −1 (w) das Wort u, f¨ ur welches der Abstand von E(u) und w minimal ist. Wir setzen π 0 = (E −1 (e1 ) . . . E −1 (eν )). Sei T = {τ ∈ {0, 1}r1 | Pr0 [V akzeptiert ϕ bei Beweis π V und Zufallsbits (τ, τ 0 )] > τ

Dann gilt: Pr[τ ∈ T ] > 1/4. Denn w¨ are Pr[τ ∈ T ] ≤ 1/4, so h¨ atten wir 1 3 1 1 1 < p∗ ≤ · + · 1 < . 2 4 4 4 2

44

1 }. 4

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Wir zeigen nun, daß V1 f¨ ur τ ∈ T die Eingabe ϕ und den Beweis π 0 akzeptiert. Seien dazu q1 , . . . , qd1 die Anfragen, die V1 (ϕ, τ ) generiert. Dann simuliert V (ϕ, τ, τ 0 ) den Verifizierer V2 auf der Eingabe Fϕ,τ mit Zufallsstring τ 0 und L¨ osung (eq1 , . . . , eqd1 , fτ ) und Beweis ρτ . Weil Prτ [V2 akzeptiert] > 1/4 (weil τ ∈ T ), folgt aus der Korrektheit von V2 , daß (E −1 (eq1 ), . . . , E −1 (eqd1 ), E −1 (fτ )) eine erf¨ ullende Belegung von Fϕ,τ ist. ⇒ (E −1 (q1 ), . . . , E −1 (qd1 )) erf¨ ullt Φ(ϕ, τ ). ⇒ V1 akzeptiert bei Eingabe ϕ, Zufallsstring τ , Beweis π 0 . ⇒ Prτ [V1 akzeptiert ϕ, τ, π 0 ] ≥ Pr[τ ∈ T ] > 1/4. ⇒ ϕ ist erf¨ ullbar. Ressourcenbedarf: Zufallsbits: r1 + r2 (poly(b1 )) Anzahl der Bl¨ ocke des Beweises, die gelesen werden: O(1) L¨ ange der Bl¨ ocke: b2 (poly(b1 ))

Das P CP -Theorem ist nun eine unmittelbare Konsequenz des Kompositionslemmas und der Resultate aus Kapitel 4 und 5. Kapitel 5 ⇒ (V1 ) 3SAT ∈ P CP (log n, poly(log n), 1) (V2 ) (RE3SAT , E10 ) ∈ P CS(log n, poly(log n), 1) Anwenden des Kompositionslemmas ergibt: (V10 ) E3SAT ∈ P CP (log n, poly(log log n), 1) Aus Kapitel 4 wissen wir, daß (V20 ) (RE3SAT , E00 ) ∈ P CS(n3 , 1, 1). Anwenden des Kompositionslemmas zeigt, daß E3SAT ∈ P CP (log n + poly(log log n), 1, 1) = P CP (log n, 1, 1). Andererseits ist P CP (log n, 1) ⊂ N P. Denn: Z¨ ahle alle Zufallsstrings (der L¨ ange log n) auf, rate Beweis, simuliere f¨ ur diesen Beweis und alle Zufallsstrings V; bei Majorit¨ at von Nichtakzeptanz akzeptiere nicht, sonst akzeptiere.

7 Nichtapproximierbarkeit von M AX(E)3SAT Ziel: Ein Beweis, daß es N P -schwer ist, M AX(E)3SAT auf einen Faktor 7/8 + ε zu approximieren, ε > 0 bel. klein, aber konstant.

7.1 Vorbemerkungen Das P CP -Theorem impliziert folgendes: Satz 13. Es gibt eine Zahl ε > 0, so daß es N P -schwer ist, M AX3SAT auf einen Faktor > 1 − ε zu approximieren.

45

Vorlesung 03.06.04

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Beweis:. Antithese: Angenommen es gibt f¨ ur alle ε > 0 einen polynomiellen Algorithmus, der M AX3SAT auf 1 − ε approximiert. Sei L eine N P -vollst¨ andige Sprache. Aus dem P CP -Theorem folgt, daß L einen (log n, 1)-Verifizierer V hat. Sei x ∈ {0, 1}∗ , |x| = n. V bekommt zus¨ atzlich noch log n Zufallsbits als Eingabe. F¨ ur jede Folge von Zufallsbits y w¨ ahlt V q = O(1) Bits aus dem Beweis aus, und gibt ein Schaltnetz Cx,y der Gr¨ oße poly(q) mit q Eing¨ angen aus. Da q = O(1) ist, hat Cx,y eine konstante Gr¨ oße. Wir wissen, daß es eine 3SAT -Formel ϕx,y mit Variablen z1 , . . . , zq (Eing¨ ange von Cx,y ) und v1 , . . . , vm gibt, wobei m = q O(1) = O(1), so daß Cx,y (π1 , . . . , πq ) = 1 gdw. ∃ Belegung f¨ ur v1 , . . . , vm , so daß ϕx,y (π1 , . . . , πq , v1 , . . . , vm ) wahr ist. Die Formeln ϕx,y sind in Polynomzeit berechenbar und haben konstante Gr¨ oße. Nun gibt es 2O(log n) = nO(1) m¨ ogliche Folgen von Zufallsbits. Die Konjunktion ϕx ≡ ∧y ϕx,y hat Gr¨ oße nO(1) . Dabei werden die Variablen z1 , . . . , zq f¨ ur die Eing¨ ange in den Formeln ϕx,y durch die von V ausgew¨ ahlten Variablen πν0 1 , . . . , πν0 q ersetzt, 0 wobei man den Beweis π als Belegung von Variablen (π10 , . . . , π|π| ) betrachtet und ν1 , . . . , νq die q Anfragen sind, die V bei Eingabe x, y generiert. Aus der Vollst¨ andigkeit folgt: Wenn x ∈ L, so gibt es einen Beweis π, so daß f¨ ur alle y gilt Cx,y (πν1 , . . . , πνq ) = 1. D.h. ϕx ist erf¨ ullbar, da alle ϕx,y erf¨ ullbar sind und die Belegungen sich auch nicht widersprechen. Ist x ∈ / L, so folgt aus der Korrektheit, daß mindestens 3/4 der ϕx,y nicht erf¨ ullbar sind, also eine Klausel haben, die nicht erf¨ ullt wird. Sei κ = nO(1) die Anzahl der Folgen von Zufallsbits. Dann sind in ϕx mindestens (3/4)κ Klauseln nicht erf¨ ullt (f¨ ur jedes π). Sei λ = O(κ) die Anzahl der Klauseln in ϕ. Dann werden in ϕx entweder alle Klauseln erf¨ ullt, oder weniger als λ − (3/4)κ. W¨ ahle εx < 3/(8(λ/κ)) (existiert) (⇒ (1 − εx )λ ≥ λ − 83 κ) Wende den (1 − εx )-Approximationsalgorithmus auf ϕx an. Sind mehr als (1 − εx )λ Klauseln erf¨ ullt, so ist x ∈ L, sonst ist x ∈ / L. Somit kann in Polynomzeit entschieden werden, ob x ∈ L oder nicht. Damit w¨ are P = N P. 7.1.1 Beweissysteme Ein Beweissystem besteht aus einem Verifizierer (z.B. einer polynomzeitbeschr¨ ankten Turing-Maschine) und einigen “Orakeln” oder “Beweisern”, welche den Verifizierer von einer Aussage vom Typ x ∈ L (x: Wort und L: Sprache) zu “¨ uberzeugen” versuchen. Sei Σ ein Alphabet. Ein Orakel ist eine Abbildung Σ∗ → {0, 1}∗. Idee: Das Orakel “antwortet” auf gewisse Fragen . Exakte Definition: Ein Verifizierer V mit einem Orakel π : Σ∗ → {0, 1}∗ ist eine polynomzeitbeschr¨ ankte Turing-Maschine zusammen mit der Abbildung π, so daß V auf eine Eingabe x und einen Zufallsstring r ∈ {0, 1}∗ zugreift und eine Ausgabe (0 oder 1) produziert, welche durch V π (x, r) bezeichnet wird. Falls V π (x, r) = 1, akzeptiert (V, π) die Eingabe x bei Zufallsstring r, sonst lehnt (V, π) ab.

46

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

W¨ ahrend der Berechnung kann V Anfragen an π stellen. Diese werden auf ein daf¨ ur vorbehaltenes Band der Turing-Maschine geschrieben. Geht V in einen ausgezeichneten Zustand zπ u ur ¨ber, so schreibt π seine Antwort auf eine weiteres (speziell daf¨ vorgesehenes) Band. Dies wird als ein Schritt von V gez¨ ahlt. Seien ρ, q : N → N Funktionen. Seien c, s ∈ R so, daß 1 ≥ c > s ≥ 0. Ein P CP ∗ (ρ, q)Verifizierer f¨ ur eine Sprache L ist eine Orakel-Turing-Maschine V (mit polynomieller Laufzeit), so daß folgendes gilt: 1. ∀ x ∈ L : ∃ Orakel π :

Pr[V π (x, r) = 1] ≥ c r

Hierbei ist r ∈ {0, 1}ρ(|x|) zuf¨ allig. 2. ∀ x ∈ / L : ∀ Orakel π :

Pr[V π (x, r) = 1] ≤ s r

Hierbei gilt: Auf Eingabe (x, r) f¨ uhrt V eine Berechnung durch, deren Resultat von q Anfragen an das Orakel π und den Antworten von π abh¨ angt. Die Antworten des Orakels sind einzelne Bits. Die Zahl c heißt dabei die Vollst¨ andigkeit des Verifizierers und s heißt Korrektheit des Verifizierers. Die Klasse P CP ∗ (ρ, q) besteht aus allen Sprachen L, die einen (O(ρ), O(q))-Verifizierer besitzen. Satz 14. Sei L ∈ N P. Sei x ∈ {0, 1}∗. Es gibt eine Zahl c < 1, so daß man in Polynomzeit eine E3SAT -Instanz ϕx,L konstruieren kann, die folgende Eigenschaften hat: 1. Ist x ∈ L, so ist ϕx,L erf¨ ullbar. 2. Ist x ∈ / L, so ist ϕx,L < c-erf¨ ullbar; d.h. hat ϕx,L m Klauseln, so erf¨ ullt keine Belegung der Variablen in ϕx,L mehr als cm Klauseln. 3. Jede Variable tritt in ϕx,L genau 5 mal auf. Der Beweis ist in [5] nachzulesen. Eine weitere Variante von Beweisern sind interaktive 2-Beweiser-1-Runde-Protokolle “M IP (2, 1)”. Der Verifizierer hat hierbei Zugriff auf 2 Orakel, kann aber jedem Orakel nur 1 Frage stellen. Beide Anfragen an die Orakel erfolgen gleichzeitig - ebenso wie die Antworten der Orakel. Die Antworten der Orakel k¨ onnen prinzipiell beliebig groß sein. (Jedoch darf der Verifizierer auf Grund seiner polynomiellen Zeitbeschr¨ ankung nur polynomiell viele Bits lesen.) Seien 1 ≥ c > s ≥ 0. Eine Polynomzeitbeschr¨ ankte Turing-Maschine V ist ein Verifizierer in einem M IP (2, 1) mit Vollst¨ andigkeit c und Korrektheit s f¨ ur eine Sprache L, falls f¨ ur jede Eingabe x ∈ {0, 1}∗ folgendes gilt: F¨ ur einen zuf¨ alligen String r ∈ {0, 1}∗ produziert V auf Eingabe (x, r) zwei Strings q1 und q2 (als Anfragen an das Orakel).

47

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

V geht in seinen Orakelzustand zπ u alt die Antworten P1 (q1 ) und ¨ber und erh¨ P2 (q2 ) der Orakel u ¨bermittelt. Mit Hilfe dieser Antworten setzt V seine Berechnung fort und akzeptiert schließlich oder lehnt ab. Dabei gilt: 1. Falls x ∈ L, so gibt es 2 Orakel P1 und P2 so, daß Pr[V (x, r, P1 (q1 ), P2 (q2 )) = 1] ≥ c r

2. Falls x ∈ / L, so gilt f¨ ur alle Paare (P1 , P2 ) von Orakeln: Pr[V (x, r, P1 (q1 ), P2 (q2 )) = 1] ≤ s r

Hierbei bezeichnet V (x, r, P1 (q1 ), P2 (q2 )) ∈ {0, 1} das Ergebnis der oben beschriebenen Berechnung. Anmerkung: Die Orakel haben Zugriff auf die Eingabe x, jedoch nicht auf den Zufallsstring r und das Ergebnis des jeweils anderen Orakels auf dessen Anfrage. M IP (2, 1) ist dann die Klasse aller Sprachen L, die einen solchen Verifizierer besitzen. Anmerkung: Es gilt M IP (2, 1) = N EXP T IM E Nehme nun an, daß der Verifizierer Vollst¨ andigkeit c = 1 hat. Ziel ist, die Korrektheit s zu verbessern. 1. M¨ oglichkeit: sequentielle Wiederholung des Protokolls. Eine u-fache Wiederholung senkt die Korrektheit auf su . Problem: Das neue Protokoll hat u Runden! 2. M¨ oglichkeit: parallele Wiederholung. Sei u ∈ N. Die u-fache parallele Wiederholung von V ist das folgende M IP (2, 1) V ⊗u : der neue Verifizierer V ⊗u wiederholt die zuf¨ allige Entscheidung von V u-mal (i) (i) unabh¨ angig, um Anfragen (q1 , q2 ) i = 1, . . . , u zu generieren. (1)

(u)

(1)

(u)

V ⊗u sendet die Anfrage (q1 , . . . , q1 ) an P1 und Anfrage (q2 , . . . , q2 ) an P2 (gleichzeitig) (i)

(i)

V ⊗u erh¨ alt von P1 und P2 eine Folge von u Antworten (a1 , a2 )i=1,...,u und (i) (i) (i) (i) akzeptiert, falls der alte Verifizierer die Antworten (a1 , a2 ) auf (q1 , q2 ) f¨ ur alle i ∈ {1, . . . , u} akzeptieren w¨ urde. Die Antwortgr¨ oße eines M IP (2, 1)-Verifizierers ist die gr¨ oßte L¨ ange der Antworten der Orakel P1 und P2 in einer akzeptierenden Berechnung von V . Satz 15. (Satz von Raz) Sei d ∈ N und 0 < s < 1. Dann gibt es eine Zahl 0 < cd,s < 1, so daß f¨ ur jeden M IP (2, 1)-Verifizierer V mit Antwortgr¨oße ≤ d und Korrektheit ≤ s folgendes gilt: F¨ ur jedes u ∈ N ist die Korrektheit von V ⊗u ≤ cud,s Der Beweis ist in [11] nachzulesen.

48

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Graphen und Algorithmen II 7

7.1.2 Die Fouriertransformierte Wir stellen boolesche Werte durch ±1 dar: −1= ˆ wahr, 1= ˆ falsch. Die Operationen ∨, ∧, ¬ werden in der nat¨ urlichen Weise f¨ ur ±1 gebraucht. Sei U eine Menge boolescher Variablen. Dann ist {−1, 1}U = {x | x : U → {−1, 1}} die Menge aller Belegungen der Variablen in U . Ist U ⊂ W , x ∈ {−1, 1}W , so ist x|U die Belegung U → {−1, 1}, u 7→ x(u). Ist α ⊂ {−1, 1}W , so ist π U (α) = {y|U | y ∈ α}. Ferner ist π2U (α) = {x ∈ {−1, 1}U | 2 - #{y ∈ α | y|U = x}}.

Oft wird das Superskript U weggelassen. Sei FU = {f | f : {−1, 1}U → {−1, 1}}. Unser besonderes Interesse gilt Abbildungen FU → {−1, 1}. Sei x ∈ {−1, 1}U . Der Langcode von x ist die Abbildung Ax : FU → {−1, 1}, f 7→ f (x). Identifiziert man Ax mit seiner Wertetabelle, so hat Ax eine Codierungsl¨ ange von 2#U . Die Beweise der P CP -Resultate beruhen auf der Fourier-Analysis von Funktionen FU → {−1, 1}. Sei u = #U. Q Definition. Sei α ⊂ {±1}U . Dann heißt χα : FU → {±1}, f 7→ x∈α f (x) ein Charakter. Sind A, B : FU → {±1}, so setzen wir hA, Bi := 2−2

u

X

A(f )B(f ).

f ∈FU

Bez¨ uglich dieses Skalarproduktes bilden die Charaktere (χα )α⊂{±1}U eine Orthonormalbasis. Definition. Sei A : FU → {±1}. Die Zahlen Y U X Aˆα = hA, χα i = 2−2 A(f ) f (x) (α ⊂ {±1}U ) x∈α

f ∈FU

heißen die Fourierkoeffizienten von A. Fourier-Inversionsformel: A(f ) =

X

Aˆα χα (f ) =

α∈{±1}U

Parseval-Identit¨ at:

X

Aˆα

α∈{±1}U

X

U Aˆ2α = 2−2

X

f ∈FU

α⊂{±1}U

49

Y

x∈α

f (x) (f ∈ FU )

A2 (f ).

Vorlesung 15.06.04

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Sei x0 ∈ {±1}U , sei A = Ax0 . Dann gilt: Aˆ{x0 } = 1 und Aˆα = 0 f¨ ur α 6= {x0 }, denn es gilt Ax0 = χ{x0 } . Lemma 12. Sind f, g ∈ FU , α ⊂ {±1}U . Dann gilt: χα (f · g) = χα (f )χα (g). Beweis:. Seien f, g ∈ FU , α ⊂ {−1, 1}U . Y Y Y Y g(x) = χα (f )χα (g) f (x) · f (x)g(x) = (f g)(x) = χα (f g) = x∈α

x∈α

x∈α

x∈α

Lemma 13. Ist f ∈ FU und sind α, β ⊂ {±1}U , so ist χα (f )χβ (f ) = χα4β (f ),wobei α 4 β = (α ∪ β) \ (α ∩ β) Lemma 14. Seien k ≥ 1 ganzzahlig U1 , . . . , Uk boolescher Variablen αi ⊂ {±1}Ui fi eine Zufallsvariable mit Bildern in FUi f¨ ur (i = 1, .., k) Sei weiterhin i0 ∈ {1, .., k} so, daß f¨ ur ein x0 ∈ αi0 der Wert fi0 (x0 ) ∈ {±1} gleichverteilt ist und unabh¨angig von den Werten fi (x), wobei (i, x) 6= (i0 , x0 ) f¨ ur x ∈ αi . Dann gilt: k Y E( χαi (fi )) = 0, i=1

wobei der Erwartungswert E genommen wird u ¨ ber zuf¨allige f1 , . . . , fk . Beweis:. E[

k Y

i=1

χαi (fi )] = E[

k Y Y

fi (x)] = E[fi0 (x0 )]E[

Y Y

i6=i0 x∈αi

i=1 x∈αi

fi (x)

Y

fi0 (x)],

x0 6=x∈αi0

da fi0 (x0 ) unabh¨ angig von fi (x)∀ (i, x) 6= (i0 , x0 ), x ∈ αi . Weil fi0 (x0 ) gleichverteilt Qk ist, gilt E[fi0 (x0 )] = 0. Somit gilt E[ i=1 χαi (fi )] = 0.

Insbesondere ist E(χα (f )) = 0, wenn α 6= ∅ und f zuf¨ allig gleichverteilt ist. Seien U, W Mengen von booleschen Variablen, U ⊂ W. Dann kann man f ∈ FU fortsetzen zu einer Abbildung {±1}W → {±1}, y 7→ f (y|U )

Lemma 15. Seien U, W Mengen boolescher Variablen mit U ⊂ W . Sei f ∈ FU . F¨ ur β ∈ {±1}W gilt: χβ (f ) = χπ2u (β) (f )

50

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Graphen und Algorithmen II 7

Sei A : FU → {±1}. Dann m¨ ochten wir “k¨ unstlich” sicher stellen, daß A(−f ) = −A(f ). (F¨ ur A = Ax , x ∈ {±1}U , gilt dies bereits.) Dazu konstruieren wir eine neue Abbildung Atrue wie folgt: W¨ ahle aus jedem Paar (f, −f ), f ∈ FU eine der Komponenten aus. Falls f gew¨ ahlt wurde, setze Atrue (f ) = A(f ) und Atrue (−f ) = −A(f ), falls −f gew¨ ahlt wurde, setze Atrue (−f ) = A(−f ) und Atrue (f ) = −A(−f ). Atrue heißt Faltung von A u ¨ber true. Es gilt: Atrue (−f ) = −Atrue (f ). ˆα 6= ∅, daß 2 - #α. Lemma 16. Ist B = Atrue , so gilt f¨ ur alle α ⊂ {±1}U mit B Insbesondere ist α 6= ∅. Beweis:. Sei B = Atrue und gelte 2|#α. Dann haben wir ˆα B

Def

=

2−2

u

X

B(f )

f ∈FU

=

2−2

u

−1

Y

f (x)

x∈α

X

B(f )

2−2

u

−1

X

B(f )

f,−f ∈FU

=

f (x) + B(−f )

Y

f (x) − B(f )

x∈α

f,−f ∈FU

=

Y

x∈α

Y

x∈α

Y

−f (x)

f (x)

x∈α

0,

da B(f ) = Atrue (f ) = −Atrue (−f ) = −B(−f ) und f¨ ur 2|#α ˆα 6= 0 : 2 - #α. gilt. Somit gilt f¨ ur alle α ⊂ {±1}U mit B

Q

x∈α

−f (x) =

Q

x∈α

f (x)

Sei A : FU → {±1}. Sei h ∈ FU . Dann setzen wir Ah : FU → {±1}, f 7→ A(h ∧ f ). Ah heißt A bedingt auf h. Lemma 17. Seien A : FU → {±1} h ∈ FU B = Ah Falls α ⊂ {±1}U die Eigenschaft hat, daß es ein x ∈ α gibt, so daß h(x) = 1, so gilt: ˆα = 0. B P Q ˆα = 2−2u Beweis:. Es gilt: B f ∈FU B(f ) x∈α f (x). Sei x0 ∈ α so, daß h(x0 ) = 1. Zu f ∈ FU definiere f 0 ∈ FU durch f 0 (x0 ) = −f (x0 ), f 0 (x) = f (x) (x 6= x0 ). Dann ist die Abbildung FU → FU , f 7→ f 0 eine Bijektion und f 00 = f. Ferner gilt: B(f ) = B(f 0 ). Also: −2u X Y X Y ˆα = 2 [ B(f ) f (x) + B(f 0 ) B f 0 (x) ] = 0. | {z } 2 x∈α x∈α f f0 B(f ) | {z } Q −

51

x∈α

f (x)

Vorlesung 17.06.04

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Sei A : FU → {±1}, h ∈ FU . Dann w¨ ahle man f¨ ur jedes g ∈ FU eine der beiden Funktionen g ∧ h, −g ∧ h aus. Setze f¨ ur f ∈ FU Ah,true (f ) = A(f ∧ h), falls f ∧ h ausgew¨ ahlt wurde und Ah,true (f ) = −A(−f ∧ h), falls −f ∧ h ausgew¨ ahlt wurde. Dann gilt: 1. Ah,true (−f ) = −Ah,true (f ) 2. der Wert von Ah,true (f ) h¨ angt nur von f ∧ h ab.

7.2 Der Langcode 7.2.1 Das 2-Beweiser Protokoll Sei ϕ eine E3SAT -Instanz mit n Variablen x1 , . . . , xn und m Klauseln C1 , . . . , Cm , so daß gilt: 1. Jede Klausel hat genau 3 Variablen 2. Jede Variable tritt genau 5-mal auf 3. Entweder ϕ ist erf¨ ullbar, oder ϕ ist ≤ c-erf¨ ullbar f¨ ur eine Konstante c < 1. Es ist N P -schwer, f¨ ur solche Formeln ϕ zu entscheiden, ob ϕ erf¨ ullbar ist. Die Variablen in der Klausel Cj seien xaj , xbj , xcj . j k P1  - V  - P2 ? 0/1 Basisprotokoll: Eingabe: ϕ 1. W¨ ahle j ∈ {1, . . . , m} zuf¨ allig. W¨ ahle k ∈ {aj , bj , cj } zuf¨ allig. Sende j an P1 und k an P2 . 2. P1 antwortet Werte f¨ ur xaj , xbj , xcj P2 antwortet einen Wert f¨ ur xk . 3. Der Verifizierer akzeptiert gdw. die Werte, die P1 , P2 zur¨ uckgeliefert haben, konsistent sind und Cj erf¨ ullen. Lemma 18. Ist ϕ c-erf¨ ullbar, so akzeptiert das Protokoll mit Wahrscheinlichkeit ≤ 2+c . 3 Beweis:. Die m¨ oglichen Antworten von P2 definieren eine Belegung (ˆ x1 , . . . , x ˆn ) der Variablen von ϕ. Diese Belegung erf¨ ullt ≤ c · m Klauseln. Die Wahrscheinlichkeit, daß (ˆ xi )i die gew¨ ahlte Klausel Cj erf¨ ullt, ist ≤ c. Falls das nicht der Fall ist, hat P1 2 M¨ oglichkeiten

52

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

1. P1 liefert eine Belegung von xaj , xbj , xcj , die mit (ˆ x aj , x ˆ bj , x ˆ cj ) u ¨bereinstimmt, aber Cj nicht erf¨ ullt. ⇒ V lehnt ab. 2. P1 liefert eine Belegung (˜ x aj , x ˜ bj , x ˜cj ) 6= (ˆ x aj , x ˆ bj , x ˆcj ) zur¨ uck, die Cj erf¨ ullt. Dann ist die Wahrscheinlichkeit, daß x ˜k 6= x ˆk , aber 1/3. ⇒ Pr[V lehnt ab] ≥ 13 . Insgesamt folgt: Pr[V lehnt ab] ≥ Problem:

2+c 3

1−c 3

ist ziemlich nah bei 1.

Das u-fach parallele Protokoll: Eingabe: ϕ 1. F¨ ur i = 1, . . . , u W¨ ahle eine zuf¨ allige Klausel Cji und darin eine zuf¨ allige Variable xki . Sende die Anfrage (j1 , . . . , ju ) an P1 und die Anfrage (k1 , . . . , ku ) an P2 . 2. P1 antwortet eine Belegung der Variablen (xaji , xbji , xcji )i=1,...,u , P2 antwortet eine Belegung der Variablen (xki )i=1,...,u . 3. Akzeptiere gdw. f¨ ur alle i ∈ {1, . . . , u} die Belegung f¨ ur (xaji , xbji , xcji ) und xki konsistent sind und die Klausel Cji durch (xaji , xbji , xcji ) erf¨ ullt ist. Der Satz von Raz (s. Seite 48) impliziert das folgende Resultat. Lemma 19. Ist ϕ c-erf¨ ullbar, c < 1, so gibt es eine Zahl γc < 1, so daß f¨ ur alle u und f¨ ur je zwei Beweiser (P1 , P2 ) folgendes gilt: der Verifizierer akzeptiert mit Wahrscheinlichkeit ≤ γcu . Ist ϕ erf¨ ullbar, so gibt es zwei Beweiser (P1 , P2 ) f¨ ur die der Verifizierer mit Wahrscheinlichkeit 1 akzeptiert. Mit U bezeichnen wir die Menge der Variablen, deren Werte der Verifizierer von P2 erfragt, und mit W die Menge der Variablen, die der Verifizierer von P1 erfragt. Um das Protokoll in ein P CP zu verwandeln, werden die Antworten der Beweiser geeignet codiert. Zu jeder m¨ oglichen Anfrage (U, W ) schreiben wir dazu den Langcode der Antwort nieder. alt zu jeder Menge V Der Standardbeweis SW P (u) (“standard written proof”) enth¨ #V von Variablen, #V ≤ 3u, einen String der L¨ ange 22 , der als Wertetabelle einer 3u Funktion AV : FV → {±1} aufgefaßt wird. Die L¨ ange des SW P (u) ist Θ(n3u 22 ) = poly(n). Ein SW P (u) heißt zudefkorrekt, falls es eine Belegung x der Variablen in ϕ gibt, so daß f¨ ur alle V wie oben gilt: AV = Ax|V . Die Bedingung von AV auf h ∈ FV wird bezeichnet durch AV,h . Die Faltung von AV,h u ¨ber wahr wird durch AV,h,true bezeichnet. Idee:

1. Baue einen Test f¨ ur den Beweis SW P (u), der dem zu untersuchenden Optimierungsproblem ¨ ahnelt, f¨ ur das ein Nichtapproximierbarkeitsresultat gezeigt werden soll. 2. Zeige, daß, falls SW P (u) den Test mit gen¨ ugend großer Wahrscheinlichkeit besteht, sich daraus eine Erfolgsstrategie f¨ ur die Beweiser in dem oben definierten Protokoll herleiten l¨ aßt.

53

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

7.2.2 Test des Langcodes Das Ziel dieses Abschnitts ist es, mit dem Langcode vertraut zu werden. Der Test wird sp¨ ater problemspezifisch durchgef¨ uhrt. Sei U eine Menge boolescher Variablen. Gegeben ist eine Funktion A : FU → {±1}. Zu testen ist, ob A ein Langcode ist, d.h. ob ∃ x ∈ {±1}U ∀f ∈ FU A(f ) = f (x).

(4)

Ziel: zu gegebenem A eine “kleine” Menge von Kandidaten x ∈ {±1}U ermitteln. 1.Versuch: u

Wir erwarten als Beweis einen String der L¨ ange 22 , interpretiert als Wertetabelle einer Funktion A : FU → {±1}. gew¨ unschte Eigenschaft: (4) 1. W¨ ahle f0 , f1 ∈ FU zuf¨ allig 2. Setze f2 = f0 f1 (d.h. ∀ x ∈ {±1}U | f2 (x) = f1 (x)f0 (x)) 3. Akzeptiere gdw. A(f0 )A(f1 )A(f2 ) = 1. Ist A ein Langcode von x0 ∈ {±1}U , so gilt: A(f0 )A(f1 )A(f2 ) = f0 (x0 )f1 (x0 )f2 (x0 ) = f0 (x0 )f1 (x0 )f0 (x0 )f1 (x0 ) = [f0 (x0 )f1 (x0 )]2 = 1 ⇒ der Verifizierer akzeptiert einen Langcode mit Wahrscheinlichkeit 1. Zu analysieren bleibt die Wahrscheinlichkeit, daß ein Beweis A akzeptiert wird, der kein korrekter Langcode ist. Also: Angenommen A : FU → {±1} ist so, daß 1+δ (δ > 0). 2 Wir wollen zeigen, daß dann A eine besondere Struktur hat. Falls Pr[Verifizierer akzeptiert A] =

Pr [A(f0 )A(f1 )A(f2 ) = 1] =

f0 ,f1

folgt

1+δ 2

1−δ 1+δ −1· = δ. 2 2 Wir wenden nun die Fourier-Inversionsformel (s. Seite 49) auf A an: X A(fi ) = Aˆα χα (fi ). Ef0 ,f1 [A(f0 )A(f1 )A(f2 )] = 1 ·

α⊂{±1}U

54

Vorlesung 22.06.04

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Daraus folgt, daß Ef0 ,f1 [A(f0 )A(f1 )A(f2 )] X = Ef0 ,f1 [ α0 ,α1 ,α2

=

Aˆα0 Aˆα1 Aˆα2 χα0 (f0 )χα1 (f1 )χα2 (f2 )]

⊂{±1}U

X

Aˆα0 Aˆα1 Aˆα2 Ef0 ,f1 [χα0 (f0 )χα1 (f1 )χα2 (f2 )]

X

Aˆα0 Aˆα1 Aˆα2 Ef0 ,f1 [χα0 (f0 )χα2 (f0 )χα1 (f1 )χα2 (f1 )]

X

Aˆα0 Aˆα1 Aˆα2 Ef0 [χα0 4α2 (f0 )]Ef1 [χα1 4α2 (f1 )].

α0 ,α1 ,α2 ⊂{±1}U

=

α0 ,α1 ,α2

=

⊂{±1}U

α0 ,α1 ,α2 ⊂{±1}U

Falls α0 4α2 6= ∅, so ist Ef0 [χα0 4α2 (f0 )] = 0. Falls α1 4α2 6= ∅, so ist Ef1 [χα1 4α2 (f1 )] = 0. Also tragen nur die Summanden f¨ ur α0 = α1 = α2 etwas bei. P Da χ∅ (f ) = 1 ∀ f ∈ FU , haben wir δ = Ef0 ,f1 [A(f0 )A(f1 )A(f2 )] = α Aˆ3α . Nach der Parseval-Identit¨ at (s. Seite 49) gilt: X u X u u Aˆ2α = 2−2 A2 (f ) = 2−2 · 22 = 1. | {z } α f ∈FU

P

=1

P

Also folgt: δ = α Aˆ3α ≤ ( α Aˆ2α ) · maxα (Aˆα ) = maxα (Aˆα ). Daher gibt es ein α ∈ {±1}U mit der Eigenschaft, daß Aˆα

≥ δ.

(5)

P Weil α Aˆ2α = 1, gibt es < δ −2 α ⊂ {±1}U , die (5) erf¨ ullen. Also haben wir eine “kleine” Menge von α’s konstruiert, die A im wesentlichen bestimmen. Problem: Die Mengen α k¨ onnen aber groß sein! 2.Versuch Der Beweis wird wie im ersten Versuch interpretiert. Sei A : FU → {±1}. gew¨ unschte Eigenschaft: A ist ein Langcode. 1. W¨ ahle f0 , f1 ∈ FU zuf¨ allig 2. W¨ ahle µ ∈ FU zuf¨ allig, indem µ(x) =



unabh¨ angig ∀ x ∈ {±1}U . 3. Setze f2 = f0 f1 µ ∈ FU . 4. Akzeptiere gdw. A(f0 )A(f1 )A(f2 ) = 1.

55

1 mit Wahrscheinlichkeit 1 − ε −1 sonst

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Angenommen A ist der Langcode von x0 . Dann akzeptiert der Verifizierer A gdw. µ(x0 ) = 1, also mit Wahrscheinlichkeit 1−ε. Betrachte nun ein A, so daß der Verifizierer mit Wahrscheinlichkeit > 1/2 akzeptiert. Wie zuvor im 1.Versuch gilt: X Aˆα0 Aˆα1 Aˆα2 Ef0 ,f1 ,µ [χα0 (f0 )χα1 (f1 )χα2 (f2 )] Ef0 ,f1 ,µ [A(f0 )A(f1 )A(f2 )] = α0 ,α1 ,α2 ⊂{±1}U

und Ef0 ,f1 ,µ [χα0 (f0 )χα1 (f1 )χα2 (f2 )] = Ef0 [χα0 4α2 (f0 )]Ef1 [χα1 4α2 (f1 )]Eµ [χα2 (µ)]. Dieser Ausdruck ist 0, es sei denn α0 = α1 = α2 . In diesem Fall ist Eµ [χα2 (µ)] = (1 − 2ε)#α , weil Eµ [µ(x)] = 1 − 2ε. Also: Ist Pr[Verifizierer akzeptiert A] = 1+δ 2 , so haben wir X X Aˆ2α ) max(Aˆα )(1 − 2ε)#α = max(Aˆα )(1 − 2ε)#α . Aˆ3α (1 − 2ε)#α ≤ ( δ= α

α

α

α

Also gibt es ein α ⊂ {±1}U , so daß Aˆα (1 − 2ε)#α ≥ δ ⇒ #α ≤ −ε−1 log δ. Folglich haben wir ≤ δ −2 “große” Fourierkoeffizienten, die “kleinen” Mengen von Belegungen entsprechen.

7.3 Nichtapproximierbarkeit

Vorlesung 24.06.04

Ziel: Ein P CP f¨ ur E3SAT. Test Lε2 (u) Beweis: Ein SW P (u) gew¨ unschte Eigenschaft: Korrektheit des Beweises f¨ ur eine E3SAT -Formel ϕ = C1 ∧ . . . ∧ Cm angig. F¨ ur je1. W¨ ahle u zuf¨ allige Klauseln (Cji )i=1,...,u gleichverteilt und unabh¨ des i ∈ {1, . . . , u} w¨ ahle eine Variable xki aus Cji (gleichverteilt, unabh¨ angig). Sei U = {xk1 , . . . , xku }. Sei W die Menge aller Variablen, die in Cj1 , . . . , Cju vorkommen. Setze h = ∧ui=1 Cji . 2. W¨ ahle f ∈ FU zuf¨ allig. 3. W¨ ahle g1 ∈ FW zuf¨ allig. 4. W¨ ahle µ ∈ FW zuf¨ allig, indem µ(y) =



(y ∈ {±1}W ).

1 mit Wahrscheinlichkeit 1 − ε −1 sonst

5. Setze g2 = f g1 µ, d.h. g2 (y) = f (y|U )g1 (y)µ(y) (y ∈ {±1}W ). 6. Akzeptiere gdw. AU,true (f )AW,h,true (g1 )AW,h,true (g2 ) = 1.

56

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Lemma 20. Die Korrektheit des Tests Lε2 (u) ist ≥ 1 − ε. Beweis:. Sei π ein SW P (u) f¨ ur eine erf¨ ullende Belegung x0 von ϕ. Wir behaupten, daß Lε2 (u) genau dann akzeptiert, wenn µ(x0 ) = 1. Denn : AU,true (f ) = f (x0 |U ), AW,h,true (g1 ) = g1 (x0 |W ). Ferner gilt:

AW,h,true (g2 ) = g2 (x0 |W ) = f (x0 |U )g1 (x0 |W )µ(x0 |W ).

Denn:

AU (f ) = f (x0 |U ) = −AU (−f ) ∀ f

und

AW,h (−f ) = AW (−f ∧ h) = (−f ∧ h)(x|W ) = −f (x|W ) ∧ h(x|W ) = −AW,h (f ) ∀ f. Daraus folgt AU = AU,true , AW,h = AW,h,true . Lemma 21. Seien ε, δ > 0. Angenommen Lε2 (u) akzeptiert einen Beweis mit Wahrur die Beweiser P1 und P2 in dem scheinlichkeit ≥ 1+δ 2 . Dann gibt es eine Strategie f¨ 2-Beweiser-1-Runde-Protokoll, welche mit Wahrscheinlichkeit ≥ 4εδ 2 zur Akzeptanz f¨ uhrt. Beweis:. Nach der Annahme des Lemmas gilt: EU,W,f,g1 ,µ [AU,true (f )AW,h,true (g1 )AW,h,true (g2 )] = δ. Setze A = AU,true , B = AW,h,true . Fixiere U, W, h; wir berechnen Ef,g1 ,µ [A(f )B(g1 )B(g2 )]. Es gilt: Ef,g1 ,µ [A(f )B(g1 )B(g2 )] X ˆβ2 χα (f )χβ1 (g1 )χβ2 (g2 )] ˆ β1 B = Ef,g1 ,µ [ Aˆα B α,β1 ,β2

=

X

ˆ β1 B ˆβ2 Ef,g1 ,µ [χα (f )χβ1 (g1 )χβ2 (g2 )] Aˆα B

X

ˆ β1 B ˆβ2 Ef,g1 ,µ [χα (f )χπU (β ) (f )χβ1 (g1 )χβ2 (g1 )χβ2 (µ)] Aˆα B 2 2

X

ˆ β1 B ˆβ2 Ef [χα (f )χπU (β ) (f )]Eg1 [χβ1 (g1 )χβ2 (g1 )]Eµ [χβ2 (µ)] Aˆα B 2 2

X

ˆβ2 Ef [χα4πU (β ) (f )]Eg1 [χβ1 4β2 (g1 )]Eµ [χβ2 (µ)]. ˆ β1 B Aˆα B 2 2

α,β1 ,β2

=

α,β1 ,β2

=

α,β1 ,β2

=

α,β1 ,β2

Falls β1 6= β2 , so gilt Eg1 [χβ1 4β2 (g1 )] = 0. Falls α 6= π2U (β2 ), so gilt Ef [χα4π2U (β2 ) (f )] = 0. Schließlich ist Eµ [χβ (µ)] = (1 − 2ε)#β . Also: X ˆ 2 (1 − 2ε)#β . Ef,g1 ,µ [A(f )B(g1 )B(g2 )] = Aˆπ2U (β) B β β

57

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Wir haben also gezeigt, daß EU,W [

X β

ˆ 2 (1 − 2ε)#β ] Aˆπ2U (β) B β

= δ.

(6)

Wir definieren nun (randomisierte) Strategien f¨ ur P1 und P2 (die Beweiser in dem ¨ Protokoll). Diese k¨ onnen dann derandomisiert werden (→ Ubung). Wenn P2 U empf¨ angt, w¨ ahlt P2 ein zuf¨ alliges α ⊂ {±1}U unter der Verteilung 2 ˆ P (α) = Aα . Dann w¨ ahltPP2 ein uniformes x ∈ α zuf¨ allig und liefert x als Antwort zur¨ uck. (Bemerke, daß α Aˆ2α = 1)

Wenn P1 W und h empf¨ angt, w¨ ahlt P1 ein zuf¨ alliges β ⊂ {±1}W mit der Ver2 ˆ teilung P (β) = Bβ und liefert ein uniform zuf¨ alliges y ∈ β als Antwort.

Lemma 16 ⇒ Wenn P1 (bzw. P2 ) α (bzw. β) ausw¨ ahlt, so ist α 6= ∅ (bzw. β 6= ∅). Lemma 17 ⇒ jedes y, das P1 sendet, erf¨ ullt h. Also brauchen wir nur noch die Wahrscheinlichkeit abzusch¨ atzen, daß die Antworten von P1 und P2 konsistent sind. (d.h. y|U = x) Beh.: Prx,y [y|U = x] ≥ #β −1 Prα,β [α = π2U (β)]. Denn: Wenn α = π2U (β), so gibt es ein y ∈ β mit y|U = x. Die Wahrscheinlichkeit, daß dann dieses y gew¨ ahlt wird, ist #β −1 . Nach Konstruktion von P1 , P2 ist die Wahrˆ 2 . Folglich scheinlichkeit, daß (α, β) ausgew¨ ahlt wird, f¨ ur jedes Paar (α, β) genau Aˆ2α B β ur festes U, W, h die Wahrscheinlichkeit, daß P1 , P2 Erfolg haben, genau ist f¨ X ˆβ2 #β −1 . Aˆ2πU (β) B 2

β

Also ist die Gesamtwahrscheinlichkeit, daß das Protokoll akzeptiert, X ˆβ2 #β −1 ]. ≥ EU,W [ Aˆ2πU (β) B 2

β∈{±1}W

Wir verwenden die elementare Absch¨ atzung ∀ x, s > 0 gilt x−s ≥ exp(−xs) und erhalten: X X X X ˆβ2 ) 12 = ( ˆβ2 #β −1 ) −1 ˆβ2 #β −1 ) −1 ˆβ2 #β −1 2 ≤ ( 2 ( 2 . Aˆ2πU (β) B B Aˆ2πU (β) B Aˆ2πU (β) B 2

2

2

β

β

β

β

Folglich gilt: EU,W [

X

β∈{±1}W

ˆ 2 #β −1 ] ≥ EU,W [( Aˆ2πU (β) B β 2

≥ (EU,W [

58

X

ˆ 2 #β −1 2 )2 ] Aˆπ2U (β) B β

X

ˆ 2 #β −1 2 ])2 . Aˆπ2U (β) B β

β∈{±1}W

β∈{±1}W

(7)

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

−1

−1

−1 2 Wendet man nun x 2 ≥ exp( −x ) ≥ exp(−2ε#β) ≥ (1−2ε)#β 2 ) an, so folgt (4ε#β √ −1 ⇒ #β 2 ≥ 4ε(1 − 2ε)#β . Setzt man dies in (6) und (7) ein, so folgt X X ˆβ2 (1 − 2ε)#β ])2 ≥ 4εδ 2 . ˆβ2 #β −1 ] ≥ 4ε(EU,W [ Aˆπ2U (β) B Aˆ2πU (β) B EU,W [ 2

β∈{±1}W

β∈{±1}W

Vorlesung 29.06.04 SW P (u) j k P1  - V  - P2

K A

6
A
Lε2 (u)

? 0/1

Satz 16. Sei ε > 0. Dann ist es N P -schwer, M AXE3XOR auf ren.

1 2

+ ε zu approximie-

Beweis:. Sei δ = 2−d und ε > 0 so, daß (1−δ)/ 1+δ 2 ≥ 2−ε. Da wir die booleschen Werte durch ±1 darstellen, sind die 3XOR-Klauseln Produkte. Sei L ∈ N P. Sei x ∈ {0, 1}∗ ein Wort, f¨ ur das zu entscheiden ist, ob x ∈ L. Dann kann man in Polynomzeit eine E3SAT -Instanz ϕ konstruieren (in welcher jede Variable genau 5-mal auftritt), so daß x ∈ L ⇒ ϕ erf¨ ullbar, x∈ / L ⇒ ϕ ≤ c-erf¨ ullbar, wobei c < 1 von x unabh¨ angig ist.

W¨ ahle u so groß, daß γcu < 4εδ 2 , wobei γc < 1 die Konstante aus dem Lemma 19 ist. (u ist eine von x unabh¨ angige Zahl.) Wir bilden die Anwendung des Tests Lε2 (u) auf ϕ durch M AXE3XOR nach. Dazu f¨ uhren wir f¨ ur jedes Bit b des SW P (u) f¨ ur ϕ eine Variable zb ein. Die Akzeptanz von Lε2 (u) ist gleichwertig mit der Bedingung zbU,f zbW,h,g1 zbW,h,g2 = b0U,W,h,f,g1 ,g2 , wobei bU,f = Bit, das AU,true (f ) entspricht bW,h,g1 = Bit, das AW,h,true (g1 ) entspricht bW,h,g2 = Bit, das AW,h,true (g2 ) entspricht angig vom Faltungsmechanismus. b0U,W,h,f,g1 ,g2 = ±1, abh¨ Wir erstellen zun¨ achst eine gewichtete Instanz von M AXE3XOR. Die Instanz besteht ur alle aus den Klauseln C(U, W, h, f, g1 , g2 ) = [zbU,f zbW,h,g1 zW,h,g2 = b0U,W,h,f,g1 ,g2 ] f¨ m¨ oglichen U, W, h, f, g1, g2 , die der Test Lε2 (u) ausw¨ ahlen k¨ onnte. Das Gewicht der Klausel C(U, W, h, f, g1 , g2 ) ist w(C(U, W, h, f, g1 , g2 )) = Pr[Lε2 (u) w¨ ahlt U, W, h, f, g1 , g2 aus].

59

Graphen und Algorithmen II 7

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Jeder Beweis π f¨ ur Lε2 (u) entspricht dann einer Belegung der Variablen zb , und das Gesamtgewicht der erf¨ ullten Klauseln X w(C(U, W, h, f, g1 , g2 )) = Pr[Lε2 (u) akzeptiert π]. U,W,h,f,g1 ,g2 C(U,W,h,f,g1 ,g2 )(π) erf u ¨ llt

Also: x ∈ L ⇒ w(π) ≥ 1 − ε. x ∈ / L ⇒ w(π) ≤ 1+δ 2 . Denn: x ∈ L ⇒ ϕ erf¨ ullbar ⇒ Pr[Lε2 (u) akzeptiert] ≥ 1 − ε. x∈ / L ⇒ ϕ ≤ c-erf¨ ullbar ⇒ 2-Beweiser-1-Runde-Protokoll akzeptiert f¨ ur alle Beweiser P1 , P2 mit Wahrscheinlichkeit ≤ γcu < 4εδ 2 ⇒ Pr[Lε2 (u) akzeptiert] ≤ 1+δ 2 . Die Gesamtzahl der Klauseln von Cϕ = ∧U,W,h,f,g1 ,g2 C(U, W, h, f, g1 , g2 ) ist polynomiell in m = |ϕ|, denn es gibt mu M¨ oglichkeiten f¨ ur W , es gibt 3u M¨ oglichkeiten f¨ ur U , u

es gibt 22 M¨ oglichkeiten f¨ ur f , es gibt 22

3u

M¨ oglichkeiten f¨ ur g1 , g2 . u

u

⇒ Gesamt: ≤ mu 22u+2 +8 = poly(|x|) Klauseln. Zu jeder Klausel kann das Gewicht in Polynomzeit berechnet werden, so daß die gewichtete Instanz in M AXE3XOR kann in Polynomzeit berechnet werden. Ein Algorithmus f¨ ur M AXE3XOR, der das Gesamtgewicht der erf¨ ullbaren Klauseln auf einen Faktor > 1+δ 2 /(1 − ε) approximieren k¨ onnte, k¨ onnte also verwendet werden, um zu entscheiden, ob x ∈ L. Daher ist es N P schwer, (gewichtetes) M AXE3XOR besser als 1+δ 2 /(1 − ε) zu approximieren. Satz 17. F¨ ur jedes ε > 0 ist es N P -schwer, M AXE3SAT auf

7 8 +ε

zu approximieren.

Beweis:. Eine Gleichung vom Typ xyz = 1 wie in der E3XOR-Instanz aus dem Beweis vorher wird ersetzt durch 4 Klauseln x ∨ y ∨ z, x ∨ y ∨ z, x ∨ y ∨ z, x ∨ y ∨ z. (∗) Analog werden Gleichungen xyz = −1 ersetzt. Eine erf¨ ullende Belegung der XOR-Klausel erf¨ ullt dann alle Klauseln in (∗). Eine Belegung, die xyz = 1 nicht erf¨ ullt, erf¨ ullt hingegen nur 3 der Klauseln. ⇒ eine Belegung, die ≤ 21 + δ der XOR-Klauseln erf¨ ullt, erf¨ ullt ≤ 78 + δ 0 der E3SAT -Klauseln. Eine Belegung, die ≥ 1 − ε der XOR-Klauseln erf¨ ullt, erf¨ ullt ≥ 1 − ε0 der E3SAT -Klauseln. Satz 18. Sei ε > 0, k ≥ 3. dann ist es N P -schwer, M AXEkXOR auf approximieren.

1 2

+ ε zu

Beweis:. Reduktion von M AXE3XOR. Gegeben sei eine M AXE3XOR-Instanz ϕ u uge neue Variablen y1 , . . . , yk−3 in jeder Klausel hinzu. ¨ber Variablen x1 , . . . , xn . F¨ Dann haben alle Klauseln die L¨ ange k. Betrachte eine Belegung xi = x∗i , yi = yi∗ ∈ {±1}. Wir unterscheiden 2 F¨ alle: 60

Vorlesung 01.07.04

Graphen und Algorithmen II 7

1.

NICHTAPPROXIMIERBARKEIT VON M AX(E)3SAT

Qk−3

i=1 yi = 1. Sei ψ die (neue) M AXEkXOR-Instanz. Setze die Belegung xi = x∗i ∀ i in die alte Instanz ϕ ein. Dann ist # erf¨ ullter Klauseln in ϕ = # erf¨ ullter Klauseln in ψ. Qk−3 2. i=1 yi = −1. Dann ist eine Klausel li1 ⊕ li2 ⊕ li3 ⊕ y1 ⊕ . . . ⊕ yk−3 von ψ genau ∗ dann erf¨ ullt, wenn li1 ⊕ li2 ⊕ li3 = 1. Betrachte also die Belegung x∗∗ i = −xi von x1 , . . . , xn . Die Zahl der von dieser Belegung erf¨ ullten Klauseln in ϕ ist genau die # erf¨ ullter Klauseln in ψ bzgl. (x∗i , yi∗ ).

⇒ # erf¨ ullbarer Klauseln von ϕ = # erf¨ ullbarer Klauseln von ψ. Da es N P -schwer ist, M AXE3XOR auf 12 + ε zu approximieren, folgt die Behauptung. Satz 19. F¨ ur jedes δ > 0 ist es N P -schwer V ERT EXCOV ER auf ximieren.

6 7

+ δ zu appro-

Beweis:. Wir starten von dem Test Lε2 (u), ε > 0 klein genug. Bei Eingabel¨ ange n wirft der Verifizierer r = r(n) M¨ unzen. Sei y ∈ {0, 1}r der resultierende Zufallsstring. Dann konstruieren wir zu jeder Eingabe ϕ (E3SAT -Instanz) von Lε2 (u) einen Graphen Gϕ . Sicht

Vϕ

}| { z = {(y, b1 , b2 , b3 ) | y ∈ {0, 1}r , b1 , b2 , b3 ∈ {±1} so, daß der Verifizierer bei Eingabe ϕ und Zufallsstring y akzeptiert, wenn die 3 abgefragten Bits aus dem Beweis die Werte b1 , b2 , b3 haben}.

Eϕ

= {{v, w} | v = (y, b1 , b2 , b3 ), w = (z, c1 , c2 , c3 ) ∈ Vϕ ,

v, w sind nicht konsistent, d.h. v, w fordern unterschiedliche Werte f¨ ur ≥ 1 abgefragtes Bit}. 6= c2 c1 b1 b2 b3 c3 I @ MB 6 6   @B  @B  z y - V  ϕ

Gϕ = (Vϕ , Eϕ ). Es gilt: #Vϕ = 2r+2 ≤ poly(n) und r = O(ln n). Das Komplement eines V ERT EXCOV ER ist eine stabile Menge. ⇒ #Vϕ − # Knoten in opt(V C) = α(Gϕ ). Ein Beweis π induziert eine stabile Menge Iπ in dem Graphen Gϕ : Iπ

= {(y, b1 , b2 , b3 ) ∈ Vϕ | die abgefragten Bits aus π bei Eingabe ϕ, Zufallsstring y haben die Werte b1 , b2 , b3 }. 61

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

Es gilt: Pr[Verifizierer akzeptiert π] =

#Iπ . 2r

guter Fall: ϕ ist erf¨ ullbar. ⇒ ∃ π | Pr[Verifizierer akzeptiert π] ≥ 1 − ε. ⇒ α(Gϕ ) ≥ 2r (1 − ε)

⇒ V C(Gϕ ) ≤ #Vϕ − 2r (1 − ε) = 2r (3 + ε). schlechter Fall: ϕ ≤ c-erf¨ ullbar, c < 1. ⇒ ∀ π| Pr[Verifizierer akzeptiert π] ≤

1 +ε 2

1 ⇒ α(Gϕ ) ≤ 2r ( + ε), 2 denn zu jeder stabilen Menge I erh¨ alt man einen Beweis πI , so daß Pr[πI wird akzeptiert] = 2−r #I. 1 7 ⇒ V C(Gϕ ) ≥ 2r+2 − 2r ( + ε) = 2r ( − ε). 2 2 guter Fall 7 6 Quotient schechter Fall = (3 + ε)/( 2 − ε) = 7 + δ, (limε→0 δ = 0). Da es N P -schwer ist, den guten Fall vom schlechten zu unterscheiden, ist es N P -schwer, V ERT EXCOV ER auf > 67 zu approximieren.

8 Korrektheitsbeweis des LowDegreeTests Zun¨ achst eine Definition: Sei {A}i∈I eine endliche Familie, mit plurality{A}i∈I wird das in {A}i∈I am h¨ aufigsten auftretende Element bezeichnet. Falls dieses nicht eindeutig ist, w¨ ahle ein Beliebiges aus. Um die Korrektheit des LowDegTests vollst¨ andig zu beweisen, fehlte nur noch der Beweis des Satzes 6 auf Seite 29. In diesem Kapitel werden die Bezeichnungen aus Abschnitt 5.2 benutzt. Zur Erinnerung nochmal der Satz: Sei 0 < δ eine gen¨ ugend kleine Zahl. Jede Funktion g : Fk → F, deren Erfolgsrate > 1 − δ/2 ist, ist δ-nah an einem Polynom in Fd,k . Beweis:. Definiere gˆd : Fk → F durch gˆd (x) = plurality{PLdx,h ,g (0)}h∈Fk ∀ x ∈ Fk . (Zur Erinnerung: mit PLdx,h ,g wird das Polynom vom Grad d bezeichnet, das auf der Gerade durch x in Richtung h am h¨ aufigsten mit g u ¨bereinstimmt.) Im folgenden werden wir sehen: ∀ x, h gˆd (x)

= PLdx,h ,ˆgd (0).

62

(8)

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

(Dies folgt aus Lemma 27 bei geeigneter Wahl der Konstanten.) Wenn #F > 2d + 1 ist, dann ist gˆd ein Polynom vom Grad d (vgl. Lemma 3 Seite 15). Sei B = {x ∈ Fk | Pr [g(x) 6= PLdx,h ,g (0)] ≥ h∈Fk

Dann gilt:

1 }. 2

#B δ Vor. 1 . > Pr [g(x) 6= PLdx,h ,g (0)] ≥ · Pr[x ∈ B] = x,h 2 2 x 2#Fk

Aus der Definition von gˆd folgt gˆd (x) = g(x) ∀ x ∈ / B. Somit gilt g ist δ-nah an gˆd . Damit ist die Korrektheit des LowDegreeTests bewiesen. Es fehlt nur noch der Beweis von (8) aus dem Beweis von Satz 6. Der Beweis wird hier in den folgenden Abschnitten gef¨ uhrt. Dazu werden zun¨ achst einige algebraische Aussagen bewiesen. Dann folgt der Satz von Arora und Safra, aus dem dann Schritt f¨ ur Schritt das gew¨ unschte gefolgert wird.

8.1 Einige hilfreiche Aussagen aus der Algebra In diesem Abschnitt werden einige wichtige Definitionen gegeben. Außerdem werden einige Lemmata bewiesen, die uns das algebraische Handwerkszeug geben, um den Beweis f¨ ur die Korrekheit des LowDegreeTests zu vervollst¨ andigen. Definition. Sei R ein Integrit¨atsbereich, d.h. ein kommutativer Ring mit 1, wobei gilt: wenn das Produkt zweier Zahlen 0 ist, so muß auch schon eine der Zahlen 0 sein. Der Quotientenk¨orper Q(R) ist dann der K¨orper, der aus den Elementen der Form a/b besteht, wobei a ∈ R und b ∈ R \ {0}. Beispiel: Q ist der Quotientenk¨ orper von Z. Lemma 22. (Cramersche Regel) Sei A eine m × n Matrix mit Eintr¨agen aus dem Integrit¨atsbereich R, m > n. Betrachte das Gleichungssystem A · z = 0. Dann gilt: 1. Das Gleichungssystem hat eine nicht-triviale L¨osung gdw. alle n×n Submatrizen von A Determinante 0 haben. 2. Wenn das Gleichungssystem eine nicht-triviale L¨osung hat, dann gibt es eine in der Form (z1 = t1 , . . . , zn = tn ), wobei jedes ti eine Summe von Determinanten von Submatrizen von A ist. Beweis:. zu 1) Betrachte zun¨ achst Q(R), den Quotientenk¨ orper von R. Wir wissen, daß es in Q(R) eine nicht-triviale L¨ osung des homogenen Gleichungssystems gibt gdw. der Rang der Matrix nicht maximal ist. Dies ist genau dann der Fall, wenn die Determinanten aller quadratischen Submatrizen der Gr¨ oße n verschwinden. Andererseits hat das Gleichungssystem genau dann eine nicht-triviale L¨ osung in Q(R), wenn es eine nicht-triviale L¨ osung in R hat. Denn jede L¨ osung in R ist auch eine L¨ osung in Q(R). Gibt es andererseits eine nicht-triviale L¨ osung in Q(R), dann ist jedes Vielfache dieser

63

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

L¨ osung auch eine L¨ osung: Multipliziere eine L¨ osung 6= 0 mit dem kgV der Nenner der Komponenten. Dann ist das Ergebnis in R und eine L¨ osung des Gleichungssystems und nicht 0, da R ein Integrit¨ atsbereich ist. zu 2) Sei B die gr¨ oßte nicht-singul¨ are (n − l) × (n − l) Submatrix von A mit l ≥ 1. o.B.d.A:   C B , A= E D wobei C 6= 0. (Denn das Tauschen von Zeilen ¨ andert die L¨ osungsmenge nicht. W¨ aren die ersten l Spalten alle 0, so br¨ auchte man diese gar nicht zu betrachten, da die ersten l Komponenten dann frei w¨ ahlbar w¨ aren.) F¨ ur jedes u ∈ Rl l¨ aßt sich das Gleichungssystem B · y = −C · u l¨ osen. Sei nun u ˆ ∈ Rl , so daß C · u ˆ 6= 0. L¨ ose das Gleichungssystem B · y = −C · det(B)ˆ u.

Sei yˆ = − det(B) · B −1 (C · u ˆ) = −adj(B)(C · u ˆ) eine L¨ osung. Da adj(B) Determinanten von Submatrizen von B als Eintr¨ age hat, ist z = (det(B)ˆ u, yˆ) eine L¨ osung der geforderten Form. Denn offensichtlich ist z eine L¨ o sung des Gleichungssystems

C B · z = 0. Andererseits sind die Zeilen von E D Linearkombinationen
der Zeilen von C B , da sonst B nicht maximal w¨ are. Damit ist z eine L¨ osung des gesamten Gleichungssystems A · z = 0.

Definition. In F2 sei {(x0 , y) | y ∈ F} (bzw. {(x, y0 ) | x ∈ F}) die Zeile durch x0 (bzw. Spalte durch y0 ). Sei f : F2 → F eine Abbildung. Dann bezeichne das Zeilenpolynom rxf,d ∈ Fd,1 das Po0 lynom vom Grad d, welches auf der Zeile durch x0 am h¨ aufigsten mit f u ¨bereinstimmt. Mit dem Spaltenpolynom cf,d y0 ∈ Fd,1 wird das Polynom vom Grad d bezeichnet, welches auf der Spalte durch y0 am h¨ aufigsten mit f u ¨bereinstimmt. Definition. Eine Menge von Punkten {(a1 , p1 ), . . . , (a10d , p10d ) | ai , pi ∈ F ∀ i} ist ur gut beschrieben in Fd,1 , wenn es ein Polynom s ∈ Fd,1 gibt, so daß s(ai ) = pi f¨ mindestens 8d Werte von i. Lemma 23. (Berlekamp-Welch) Sei {(a1 , p1 ), . . . , (a10d , p10d )} gut beschrieben in Fd,1 . 1. Es gibt Polynome q ∈ F3d,1 und 0 6= e ∈ F2d,1 , so daß q(ai ) = e(ai )pi ∀ i ∈ {1, . . . , 10d}. 2. Gelte f¨ ur zwei Polynome q, e: q(ai ) = e(ai )pi ∀ i ∈ {1, . . . , 10d}. Dann ist q/e ein Polynom vom Grad d, welches die Menge {(a1 , p1 ), . . . , (a10d , p10d )} gut beschreibt.

64

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

Beweis:. Sei s das Polynom, welches {(a1 , p1 ), . . . , (a10d , p10d )} gut beschreibt. zu 1) Sei 0 6= e ∈ F2d,1 mit e(ai ) = 0, wenn s(ai ) 6= pi , falls dies nie eintritt, definiere e = 1. Dann gilt: e(ai )s(ai ) = pi e(ai ) ∀ i ∈ {1, . . . , 10d}. Definiere q = s · e. Die Behauptung ist dann offensichtlich erf¨ ullt. zu 2) Es gilt s(ai )e(ai ) − q(ai ) = 0, wenn s(ai ) = pi . Da s die Punkte (a1 , p1 ), . . . , (a10d , p10d ) gut beschreibt, gilt f¨ ur 8d Punkte s(ai ) = pi . Somit ist se − q = 0, denn dieses Polynom hat Grad 3d und 8d Nullstellen. Damit folgt q/e = s. Lemma 24. Sei {a1 , . . . , a10d } eine Menge von Punkten und s1 , . . . , s10d : F → F Polynome vom Grad d, so daß f¨ ur die H¨alfte der Punkte b ∈ F die Menge {(a1 , s1 (b)), . . . , (a10d , s10d (b))} gut beschrieben ist in Fd,1 . Dann gibt es Polynome q, e ∈ F[X1 , X2 ] mit e 6= 0 und GradX1 q = 3d, GradX2 q = GradX2 e = 6d2 , GradX1 e = 2d, so daß q(ai , b) = si (b)e(ai , b) ∀ b ∈ F, i ∈ {1, . . . , 10d}. Beweis:. Betrachte das lineare Gleichungssystem A · z = 0, wobei z = (v0 (y), . . . , v3d (y), u0 (y), . . . , u2d (y)) und  1 a1 . . . a3d −s1 (y) −a1 s1 (y) ... −a2d 1 1 s1 (y) 3d 2d  1 a 2 . . . a2 −s (y) −a s (y) . . . −a 2 2 2 2 s2 (y)  A= . . . . . . . .. .. .. .. .. .. ..  .. . 1 a10d

. . . a3d 10d

−s10d (y) −a10d s10d (y) . . . −a2d 10d s10d (y)



  . 

Setzt man Werte f¨ ur y ein, so erh¨ alt man #F Gleichungssysteme. F¨ ur die y-Werte, wo {(a1 , s1 (b)), . . . , (a10d , s10d (b))} gut beschrieben sind, folgt aus dem Lemma 23, daß das Gleichungssystem eine nicht-triviale L¨ osung hat. Lemma 22 besagt dann, daß alle (5d + 2) × (5d + 2) Submatrizen von A die Determinante 0 haben. Andererseits kann man auch nur ein Gleichungssystem betrachten, wobei die Eintr¨ age in A Polynome in y sind. Nach Lemma 22 besitzt dieses Gleichungssystem eine nichttriviale L¨ osung gdw. jede (5d + 2) × (5d + 2) Submatrix die Determinante 0 hat. Sei B eine quadratische Submatrix von A der Gr¨ oße 5d + 2. Dann ist die Determinante von B ein Polynom in y vom Grad (5d + 2)d. Da dieses Polynom aber nach Voraussetzung f¨ ur mehr als die H¨ alfte aller y gleich 0 ist, ist es das Nullpolynom. Lemma 22 besagt nun auch, daß es eine L¨ osung ui (y), vi (y) geben muß, die aus Polynomen vom Grad ≤ (5d + 1)d ≤ 6d2 besteht. Definiere nun q(x, y) =

3d X

vi (y)xi ∀ x, y ∈ F,

2d X

ui (y)xi ∀ x, y ∈ F.

i=0

e(x, y) =

i=0

Diese Polynome erf¨ ullen die geforderten Bedingungen.

65

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

8.2 Der Satz von Arora und Safra Der wichtigste Teil in diesem Beweis, Satz 20, folgt nun leicht aus folgendem Lemma. Lemma 25. Sei f : F2 → F so, daß f auf allen Spalten (s. Seite 64) Polynomen vom Grad d entspricht. Gibt es außerdem noch 10d Punkte in F, so daß f auf den Zeilen durch diese Punkte ε-nah an Polynomen vom Grad d ist, wobei ε ≤ 0.1 ist, dann ist f 1.5ε-nah an einem Polynom vom Grad d, falls #F ≥ kd3 , wobei k eine geeignete Konstante ist. Beweis:. Betrachte f als Matrix. Wir zeigen zun¨ achst, daß es eine Submatrix gibt, welche 2/5 der Spalten und d + 1 Zeilen enth¨ alt, so daß alle Spalten und Zeilen mit einem Polynom vom Grad d u ¨bereinstimmen. Seien a1 , . . . , a10d die Punkte in F, auf deren Zeilen f ε-nah an Polynomen vom Grad d ist. Die Polynome raf,d , . . . , raf,d (s. Seite 64) erf¨ ullen die Voraussetzungen des Lemmas 24. 1 10d Denn f¨ ur mindestens die H¨ alfte aller b ∈ F wird {(a1 , raf,d (b)), . . . , (a10d , raf,d (b))} gut 1 10d f,d f,d beschrieben durch cb , da f¨ ur festes ai , b nach Voraussetzung Pr[cf,d (a ) = 6 r i ai (b)] = ε b gilt. Bildet man nun f¨ ur festes b den Erwartungswert dar¨ uber, an wievielen Stellen von a1 , . . . , a10d Zeilen- und Spaltenpolynom u ¨bereinstimmen, so ergibt sich die Behauptung. Damit gibt es ein Polynom q ∈ F[X1 , X2 ] mit GradX1 q = 3d und GradX2 q = 6d2 und ein Polynom 0 6= e ∈ F[X1 , X2 ] mit GradX1 e = 2d und GradX2 e = 6d2 , so daß q(ai , b) = raf,d (b)e(ai , b) ∀ b ∈ F, i = 1, . . . , 10d. i f,d Wird {(a1 , raf,d (b)), . . . , (a10d , raf,d (b))} gut beschrieben durch cf,d = b , dann ist cb 1 10d q,3d e,2d cb /cb wegen Lemma 23 (2) und der Eindeutigkeit des Polynoms, das eine vorgegebene Menge gut beschreibt. Ist e(ai , b) 6= 0, so gilt: raf,d (b) = cf,d ur 8d der a1 , . . . , a10d , b (ai ). Dies gilt bei festem b f¨ i da e 6= 0 vom Grad 2d in X1 (s. Lemma 1 auf Seite 14). Wir berechnen nun den Anteil an Spalten, auf denen e eingeschr¨ ankt auf a1 , . . . , a8d nie 0 wird. Da e 6= 0 Grad 6d2 in X2 hat, hat e eingeschr¨ ankt auf eine der Zeilen a1 , . . . , a8d h¨ ochstens 6d2 Nullstellen. Damit ist die Wahrscheinlichkeit, daß auf einer Spalte e an den Stellen a1 , . . . , a8d 0 wird, 8d · 6d2 /#F. Nun gibt es (1/2) − (8d · 6d22/#F) Spalten, die durch cf,d b gut beschrieben werden, und auf denen e an den Stellen a1 , . . . , a8d nie 0 wird. W¨ ahle nun k so, daß 48d3 /#F < 0.1 ist. Dann gilt dies f¨ ur 2/5 der Spalten. Dadurch hat man die gew¨ unschte Matrix. Seien a1 , . . . , ad+1 die Zeilen, die in der soeben konstruierten Submatrix vorkommen. Wir zeigen nun, daß f 1.5ε-nah an dem Polynom φ vom Grad d ist, das definiert ist durch d+1 X φ(x1 , x2 ) = φai (x1 )raf,d (x2 ), i i=1

wobei φai (x1 ) das Polynom vom Grad d ist, welches an der Stelle ai den Wert 1 annimmt und 0 ist, wenn x1 ∈ {a1 , . . . , ad+1 } \ {ai }. Zun¨ achst stellen wir fest, daß die Zeilen durch a1 , . . . , ad+1 von φ mit denen von f nach Definition u ¨bereinstimmen. Betrachte eine Spalte b aus der oben konstruierten

66

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

Submatrix. Dann stimmt cf,d auf der Spalte mit φ u ¨berein. Damit sind f und φ ≤ 0.6b nah, da ihre Spaltenpolynome f¨ ur 2/5 der Spalten identisch sind und f auf den Spalten mit dem Spaltenpolynom u ¨bereinstimmt. Dies gilt insbesondere auch, wenn man den ersten Wert festlegt und nun die Zeilen betrachtet. Auf den Punkten, in denen die Zeilen ε-nah an Polynomen vom Grad d sind, gilt dann raf,d und raφ,d sind 0.7-nah (Dreiecksungleichung) ∀ i ∈ {d + 2, 10d}. Da beides i i Polynome vom Grad d sind, m¨ ussen sie aber gleich sein. In jeder Zeile a1 , . . . , a10d stimmt φ dann nicht mit f u ¨berein, wenn cf,d y (ai ) 6= φ(ai , y) = f,d ankung von φ auf eine Spalte aber ein Polynom vom Grad d ist, rai (y). Da die Einschr¨ muß es sich vom Spaltenpolynom von f auf den 10d Punkten in 9d Punkten unterscheiden, wenn die Polynome unterschiedlich sein sollen. Da in jeder Zeile der Unterschied aber nur bei ε der Punkte auftritt, kann nur 1.5ε der Spalten in mehr als 9d Punkten verschieden sein. (Betrachte den Erwartungswert.) Somit sind φ und f 1.5ε-nah. Satz 20. (Arora und Safra) Es gibt Konstanten ε0 , k > 0, so daß gilt: Sei d ∈ N, ε < ε0 , F K¨orper mit #F ≥ kd3 . F¨ ur f : F2 → F seien R, C : F2 → F die f,d Abbildungen mit R(x, y) = rx (y) und C(x, y) = cf,d y (x). Wenn f ε-nah an R und C ist, dann gibt es ein Polynom g : F2 → F mit Grad ≤ d in jeder Variablen, so daß f 4ε-nah an g ist. Beweis:. W¨ ahle ε0 = 0.05. Dann ist f ε-nah an einer Funktion fˆ, deren Spalten Polynomen vom Grad d entsprechen (n¨ amlich C). Außerdem ist fˆ 2ε-nah an R (Dreiecksungleichung). fˆ erf¨ ullt die Voraussetzungen des Lemmas 25 und ist somit 3ε-nah an einem Polynom g. Mit Hilfe der Dreiecksungleichung erhalten wir, daß f 4ε-nah an g ist.

8.3 Folgerungen aus dem Satz von Arora und Safra Dieser Abschnitt enth¨ alt nun alle Zwischenresultate, um von Satz 20 zum eigentlichen Beweis von (8) aus dem Beweis von Satz 6 zu gelangen. Wir schreiben kurz ∆(f, g) ≤ δ, um zu sagen, daß f und g δ-nah sind. Korollar 2. Sei f : F2 → F so, daß die Voraussetzungen des Satzes 20 erf¨ ullt sind. 2d Seien ε0 , k die Konstanten aus Satz 20. Sei 0 < ε0 < 21 − #F − 5ε. Wenn f¨ ur x0 , y0 ∈ F gilt: Pr[f (x, y0 ) 6= rxf,d (y0 )] ≤ ε0 x

und 0 Pr[f (x0 , y) 6= cf,d y (x0 )] ≤ ε , y

dann rxf,d (y0 ) = cf,d y0 (x0 ). 0 Beweis:. Aus Satz 20 folgt, daß es ein Polynom g vom Grad d in jeder Variablen gibt, so daß ∆(f, g) ≤ 4ε. Da ∆(f, C) ≤ ε und ∆(f, R) ≤ ε, folgt aus der Dreiecksungleichung ∆(g, C), ∆(g, R) ≤ 5ε. Wir zeigen nun rxf,d (y0 ) = g(x0 , y0 ) = cf,d y0 (x0 ). Sei x ∈ F. Da 0 67

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

zwei Polynome vom Grad d in einer Variablen in h¨ ochstens d Punkten u ¨bereinstimmen, wenn sie unterschiedlich sind, gilt: ∆(g, R) = Pr[g(x, y) 6= R(x, y)] ≥ (1 − x,y

d ) Pr[g(x, ·) 6= rxf,d ]. #F x

F¨ ur ε ≤ 1 − (d/#F) folgt: Prx [g(x, ·) 6= rxf,d ] ≤ 5ε + d/#F. Damit ergibt sich: Pr[f (x, y0 ) 6= g(x, y0 )] x

≤ Pr[f (x, y0 ) 6= rxf,d (y0 )] + Pr[rxf,d (y0 ) 6= g(x, y0 )] x

x

d ≤ ε0 + 5ε + #F 1 d < − . 2 #F Dies bedeutet aber, daß g(·, y0 ) = cf,d y0 . Insbesondere trifft dies also an der Stelle x0 zu. Analog folgt g(x0 , y0 ) = rxf,d (y ). 0 0 Lemma 26. Sei 0 < ε < min{1/36, ε0} und #F ≥ max{6d, kd3 }, wobei k und ε0 die Konstanten aus Satz 20 sind. Dann gilt f¨ ur jede Funktion f : Fm → F : m ∀ x ∈ F , t0 ∈ F : Pr [PLdx,h

h1 ,h2

1

d ,f (t0 ) 6= PLx+t

0 h1 ,h2

,f (0)] ≤

4 Prx,h,t [PLdx,h ,f (t) 6= f (x + th)] ε

+

4 . #F

Beweis:. Sei δ = Prx,h,t [PLdx,h ,f (t) 6= f (x+th)]. Außerdem definiere f¨ ur zuf¨ allig gew¨ ahlte h1 , h2 ∈ Fm die Funktion Mh1 ,h2 : F2 → F durch Mh1 ,h2 (y, z) = f (x + yh1 + zh2 ). Zun¨ achst gilt 6ε + 2d/#F < 1/2, denn #F ≥ 6d und ε < 1/36. Bezeichne Xh1 ,h2 ,y,z die Indikatorvarible, welche 1 ist, wenn PLdx+yh ,h ,f (z) 6= f (x + yh1 + zh2 ), und sonst 1 2 0. Weil ∀ y 6= 0, ∀ z Pr [PLdx+yh ,h ,f (z) 6= f (x + yh1 + zh2 )] ≤ δ, h1 ,h2

1

2

gilt f¨ ur alle y 6= 0und f¨ ur alle z, daß der Erwartungswert Eh1 ,h2 [Xh1 ,h2 ,y,z ] ≤ δ ist. Damit folgt: Eh1 ,h2 ,y6=0,z [Xh1 ,h2 ,y,z ] ≤ max {Eh1 ,h2 [Xh1 ,h2 ,y,z ]} ≤ δ. y6=0,z

Mit Hilfe der Markoff-Ungleichung (s. Seite 11) und der Definition von Mh1 ,h2 (y, z) erh¨ alt man δ ,d M Pr [ Pr [Mh1 ,h2 (y, z) 6= ry h1 ,h2 (z)] ≥ ε] ≤ . h1 ,h2 y6=0,z ε Nimmt man nun noch den Fall y = 0 hinzu, so erh¨ alt man die Absch¨ atzung: Mh1 ,h2 ,d

Pr [Pr[Mh1 ,h2 (y, z) 6= ry

h1 ,h2 y,z

68

(z)] ≥ ε] ≤

δ 1 + . ε #F

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

Auf ¨ ahnliche Weise erh¨ alt man auch f¨ ur beliebige, aber fest gew¨ ahlte z0 , y0 ∈ F Mh1 ,h2 ,d

Pr [Pr[Mh1 ,h2 (y, z0 ) 6= ry

h1 ,h2 y

(z0 )] ≥ ε] ≤

1 δ + , ε #F

δ 1 + , ε #F δ 1 M ,d Pr [Pr[Mh1 ,h2 (y0 , z) 6= cz h1 ,h2 (y0 )] ≥ ε] ≤ + . h1 ,h2 z ε #F Mh1 ,h2 ,d

Pr [Pr[Mh1 ,h2 (y, z) 6= cz

h1 ,h2 y,z

(y)] ≥ ε] ≤

1 Also erf¨ ullt Mh1 ,h2 mit Wahrscheinlichkeit ≥ 1 − 4( εδ + #F ) die Voraussetzungen des 0 Korollars 2 f¨ ur y0 = t0 , z0 = 0, ε = ε. Somit folgt aus Korollar 2 und der Definition von M :

PLdx,h

1

,f (t0 )

M

,d

M

,d

= cz0 h1 ,h2 (y0 ) = ry0 h1 ,h2 (z0 ) = PLdx+t

0 h1 ,h2

,f (0).

Korollar 3. Sei 0 < ε < min{1/36, ε0}, wobei ε0 und k die Konstanten aus Satz 20 sind. Wenn #F ≥ max{6d, kd3 } ist, dann gilt f¨ ur jede Funktion f : Fm → F : m ∀x∈F , t∈F: Prm [fˆd (x + th) 6= PLdx,h ,f (t)] ≤

8 Prx,h,t [PLdx,h ,f (t) 6= f (x + th)] ε

h∈F

+

8 , #F

wobei fˆd (x + th) = plurality{PLdx+th,h0 ,f (0)}h0 . Beweis:. Sei δ = Prx,h,t [PLdx,h ,f (t) 6= f (x + th)]. Definiere die Menge Bx,t = {h ∈ Fm | PLdx,h ,f (t) 6= plurality{PLdx+th,h0 ,f (0)}h0 }. Ist h ∈ / Bx,t , so gilt PLdx,h ,f (t) = fˆd (x + th) = plurality{PLdx+th,h0 ,f (0)}h0 . Daraus folgt: #Bx,t Prm [fˆd (x + th) 6= PLdx,h ,f (t)] ≤ . h∈F #Fm Lemma 26 besagt, daß Pr0 [PLdx+th,h0 ,f (0) 6= PLdx,h ,f (t)] ≤

h,h

4δ 4 + . ε #F

Da außerdem f¨ ur jedes h ∈ Bx,t Pr0 [PLdx+th,h0 ,f (0) 6= PLdx,h ,f (t)] ≥ h

gilt auch

1 , 2

#Bx,t . h,h 2#Fm Mit diesen Absch¨ atzungen ergibt sich die gew¨ unschte Ungleichung. Pr0 [PLdx+th,h0 ,f (0) 6= PLdx,h ,f (t)] ≥

69

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

8.4 Der eigentliche Beweis Nun zeigen wir schließlich die entscheidende Aussage (8) aus dem Beweis von Satz 6, indem wir die Resultate aus Abschnitt 8.3 verwenden. Lemma 27. Sei #F ≥ max{6d, kd3 } und ε = min{1/36, ε0}, wobei k, ε0 die Konstanten aus Satz 20 sind. Sei f : Fm → F so, daß gilt: 256 56δ 40 256δ + + + <1 ε2 ε#F ε #F mit δ = Prx,h,t [PLdx,h ,f (t) 6= f (x + th)]. Dann gilt: ∀ x, h ∈ Fm fˆd (x) = PLd ,fˆ (0), x,h d wobei fˆd (x) = plurality{PLdx,h0 ,f (0)}h0 . Beweis:. W¨ ahle h1 , h2 ∈ Fm zuf¨ allig. Definiere M : F2 → F durch ˆ M (y, 0) = fd (x + yh) und M (y, z) = f (x + yh + zh1 + yzh2 ) f¨ ur z 6= 0. Damit ergeben sich folgende Gleichungen: ryM,d (z) = PLdx+yh,h

1 +yh2

,f (z),

cM,d (y) = PLdx+zh1 ,h+zh2 ,f (y), z 6= 0, z cM,d (y) = PLd 0

ˆ

x,h ,fd

(y).

(0) = r0M,d (0) mit Wahrscheinlichkeit > Aus den Korollaren 2 und 3 folgt: cM,d 0 und M (0, 0) = fˆd (x) = PLdx,h ,f (0) = r0M,d (0)

8δ ε

8 + #F

1

mit Wahrscheinlichkeit ≥ 1 − 8δ/ε − 8/#F. Dazu muß aber noch gezeigt werden, daß die Voraussetzungen der Korollare erf¨ ullt sind. Die Voraussetzungen des Korollars 3 sind Teil der Voraussetzungen dieses Lemmas. Es bleibt also noch zu zeigen, daß auch die Voraussetzungen des Korollars 2 f¨ ur M, ε0 = ε, y0 = z0 = 0 gelten. Nach Definition ˆ ist M (y, z) = fd (x + yh + z(h1 + yh2 )) f¨ ur z = 0. F¨ ur z 6= 0 gilt Pr [M (y, z) 6= fˆd (x + yh + z(h1 + yh2 ))] ≤ 2δ.

h1 ,h2

Außerdem ist Pr[fˆd (x + yh + z(h1 + yh2 )) 6= PLdx+yh,h

1 +yh2

,f (z)]

≤

8 8δ + . ε #F

Somit gilt insgesamt f¨ ur die Zeilen Pr [M (y, z) 6= ryM,d (z)] ≤

h1 ,h2

8δ 8 + + 2δ = δ1 . ε #F

F¨ ur die Spalten gilt nun Pr [M (y, z) = f (x + zh1 + y(h + zh2 )) = PLdx+zh

h1 ,h2

70

1 ,h+zh2

,f (y)

= cM,d (y)] = δ. z

Graphen und Algorithmen II 8

KORREKTHEITSBEWEIS DES LOWDEGREETESTS

Nun kommt man wie im Beweis des Lemmas 26 zu den Absch¨ atzungen Pr [Pr[M (y, z) 6= ryM,d (z)] ≥ ε] ≤

h1 ,h2 y,z

Pr [Pr[M (y, 0) 6= ryM,d (0)] ≥ ε] ≤

h1 ,h2 y

Pr [Pr[M (y, z) 6= cM,d (y)] ≥ ε] ≤ z

h1 ,h2 y,z

(0)] ≥ ε] ≤ Pr [Pr[M (0, z) 6= cM,d z

h1 ,h2 z

δ1 1 + ε #F δ1 1 + ε #F δ 1 + ε #F 1 δ + . ε #F

Also sind die Voraussetzungen des Korollars 2 mit Wahrscheinlichkeit ≥ 1 − 16(

δ1 δ 2 8δ 8 + + )> + ε ε #F ε #F

erf¨ ullt wegen der Voraussetzungen dieses Lemmas. ε und δ sind so gew¨ ahlt, daß mit positiver Wahrscheinlichkeit (¨ uber h1 , h2 ) das Ereignis fˆd (x) = r0M,d (0) = PLd ,fˆ (0) eintritt. Da es aber von h1 , h2 unabh¨ angig ist, hat dieses x,h

d

Ereignis Wahrscheinlichkeit 1. Damit gilt M (0, 0) = cM,d (0). 0

71

Literatur

Graphen und Algorithmen II

Literatur [1] Arora, Lund, Motwani, Sudan, Szegedy: Proof verification and the hardness of approximation problems J. ACM 45 (1998) 501-555 [2] Arora, Safra: Probabilistic checking of proofs: A new characterization of N P J. ACM 45 (1998) 70-122 [3] Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, Protasi: Complexity and approximation. Springer (1999) [4] Emden-Weinert, Hougardy, Kreuter, Pr¨ omel, Steger: Einf¨ uhrung in Graphen und Algorithmen Online-Skript: http://www.informatik.hu-berlin.de/Institut/struktur/algorithmen/ga

[5] U. Feige: A Threshold of ln n for approximating set cover Proceedings of the 28th Annual ACM Symposium on Theory of Computing (ACM STOC 1996), Philadelphia, Pennsylvania, USA, May 1996, pp. 314-318. [6] H˚ astad: Some optimal inapproximability results J. ACM 48 (2001) 798-859 [7] H˚ astad: Clique is hard to approximate within n1− Acta Mathematica 182 (1999) 105-142 [8] Hougardy, Pr¨ omel, Steger: Probabilistically checkable proofs and their consequences for approximation algorithms Discrete Mathematics 136 (1994), 175-223 [9] Lang: Algebra Addison-Wesley (1993)

72

Literatur

Graphen und Algorithmen II

[10] Papadimitriou: Computational Complexity Addison-Wesley (1994) [11] Raz: A parallel repetition theorem SIAM J. Comput. 27 (1998) 763-803 [12] Rudin: Fourier analysis on groups. Wiley (1962) letzte Aktualisierung: 06.05.2005

73