Beweissysteme

Hartmut KlauckUniversität Frankfurt

WS 06/0724.1.

NP vs. PCP

• Wir wollen NPµ PCP(poly,O(1)) zeigen• Wir müssen ein Beweissystem für

SAT konstruieren• Wir verwenden ein anderes

vollständiges Problem stattdessen:– Quadratische Gleichungen über Z2

Hadamard Codes

• Seien x,y aus Z2n

• x±y := i xiyi mod 2 = ©i xiyi

• Definition Für ein u2 {0,1}n=Z2

n sei die Hadamard Kodierung C(u) die Tabelle der Funktion f(x)=u±x mit x2 Z2

n

• Hadamard Codeworte sind damit genau die linearen Funktionen über

• Lemma [lokale Dekodierbarkeit]Angenommen g sei -approximativ zu f=C(u).Es gibt einen Algorithmus, der mit 2 Fragen an g zu jedem x den Wert f(x) mit Ws. 1-2 bestimmt.

Hadamard Codes

• Hadamard Codes haben Distanz 2n/2, bei Codelänge 2n.

• Das bedeutet, dass für uv gilt:– f=C(u) unterscheidet sich von g=C(v) an 50%

der Eingaben, [d.h. f(x)g(x) für 50% aller x]– f(x)=u±x=i ui^xi

• Anders formuliert:– Sei uv– Wenn für eine zufällige Teilmenge Iµ{1,…,n}

alle ui bzw. alle vi mit i2 I addiert werden, unterscheidet sich das Ergebnis mit Ws. 1/2

Quadratische Gleichungen

• Eine quadratische Gleichung über Z2 ist von der Formi,jaijuiuj=b für Variablen u1...un mit Koeffizienten ai,j und b aus Z2

• Eine Instanz von QUADEQ ist eine Menge von Gleichungen über Variablen u1,…,un

• Eine Instanz ist erfüllbar, wenn alle Gleichungen simultan erfüllbar sind [durch eine Belegung von (u1,…,un) aus Z2

n]• Lemma

– QUADEQ ist NP-vollständig

Tensorprodukt

• Das Tensorprodukt u v zweier Vektoren u,v2 Z2

n ist ein n2 langer Vektor w mit w(i,j)=uivj

Das Beweissystem

• Wir wollen ein Beweissystem für QUADEQ angeben

• Eingabe ist eine QUADEQ Instanz• Wir betrachten die Eingabeinstanz wie folgt

– u1,…, un seien die Variablen (ein Spaltenvektor)– U sei ein n2-dim. Spaltenvektor mit U[i,j]=uiuj

– Wir schreiben dann auch U=u u [Tensorprodukt]– b sei ein Vektor der rechten Seiten der k Gleichungen– A sei eine k£n2 Matrix, so dass AU=b das

Gleichungssystem darstellt– Eine Instanz von QUADEQ ist somit durch A,b gegeben

QUADEQ

• Wir wollen ein Beweissystem für die Erfüllbarkeit quadratischer Gleichungssysteme über Z2

n angeben

• Wir erwarten als „korrekten“ Beweis die Hadamard Codes von u und von U=u u zu einer erfüllenden Belegung u

• g,G seien durch den PCP-Beweis gegeben• Unser Verifizierer (grob):

1. Teste, ob g und G 0.001-approximativ linear sind2. Teste ob U=u u ist3. Teste, ob u erfüllend ist ( 2.,3. mit Hilfe von g,G)

Schritt 1

• Wir haben den Linearitätstest schon angegeben.

• Mit Ws. 0.99 werden alle g,G verworfen, die nicht 0.001-approximativ linear sind

• Wir gehen daher davon aus, das es f,F gibt, die linear sind, und auf einem 0.999 Anteil ihrer Einträge mit g,G übereinstimmen

• Weiterhin können wir f(x) und F(x) für jedes x mit Ws. 0.998 bestimmen (durch je 2 Fragen an g bzw. G), wegen lokaler Dekodierbarkeit

Bemerkung

• Der restliche Test stellt nur 17 Fragen an f oder F, wir gehen daher davon aus, dass der Beweis tatsächlich f,F enthält, also Hadamard Codes von strings u,W– Denn: mit guter Ws. ist die Dekodierung

von f(x),F(x) für alle 17 Fragen erfolgreich:

– Prob(es gibt einen Fehler)· 17¢0.002<1/20

Schritt 2

• Wir wollen testen, ob W=u u1. Wiederhole 5 mal:

i. Ziehe r,r’ uniform aus Z2n

ii. Teste ob f(r)f(r’)=F(r r’)2. Akzeptiere, wenn alle Tests bestanden

• Korrekte Beweise (W=u u) werden immer akzeptiert, denn

Schritt 2

• Angenommen, WU=u u• Behauptung 13.1: Jeder der 5 Tests

in Schritt 2 verwirft mit Ws. mindestens 1/4

• Dann ist die Gesamtwahrscheinlichkeit, zu verwerfen mindestens 1-(3/4)5>3/4

Beweis der Behauptung

• Wir betrachten jetzt W als eine n£n Matrix, ebenso U

• U=u¢uT; U[i,j]=uiuj

• r sei ein Zeilenvektor, r’ ein Spaltenvektor

Beweis der Behauptung

• Dann gilt

Beweis der Behauptung

• Der Verifizierer verwirft also, wenn (für mind. ein gewähltes r,r’) gilt: rWr’rUr’

• Mindestens 1/2 aller r erfüllen rWrU wegen der Distanzeigenschaft von Hadamard Codes:– UW) es gibt i,j mit U[i,j]W[i,j]– ) rW[j] = t=1...n rtW[t,j] t rtU[t,j] =rU[j] mit

Wahrscheinlichkeit 1/2 • Für jedes r mit rWrU gilt ebenso:

– Mindestens 1/2 aller r’ erfüllen rWr’ rUr’

• Damit folgt die Behauptung, dass rWr’ rUr’ mit Ws ¸ 1/4.

Zusammenfassung 1 und 2

• Wir erhalten somit, dass der PCP-Beweis aus Hadamard Codes für u und für u u besteht, wenn Schritte 1 und 2 mit hoher Wahrscheinlichkeit bestanden wurden.

Schritt 3• Wir müssen nun noch testen, ob u eine erfüllende

Belegung ist• Zuerst betrachten wir den Fall, dass es nur eine

Gleichung gibt (die t-te Gleichung).

• Setze zt=At,( ¢, ¢) mit 1·i,j·n• Die linke Seite der Gleichung ist einfach F(zt)=U±zt,

wir wollen testen,ob F(zt)=bt

• Da der Verifizierer sowohl zt als auch bt kennt, kann er die Gleichung durch 1 Frage nach F(zt) testen

• Tatsächlich enthält der Beweis in F=C(u u) den Wert aller möglichen linken Seiten von Gleichungen

Schritt 3• Testen aller Gleichungen:• Wir können natürlich nicht einfach alle i von 1 …

k durchlaufen• Idee: der Verifizierer wählt eine zufällige

Teilmenge der Gleichungen, summiert diese modulo 2 und testet die erhaltene Gleichung

• Formal: wähle d1,..,dk zufällig• Neue Gleichung:

• Diese Gleichung kann durch 1 Frage an F getestet werden

Schritt 3

• Wenn es ein t gibt, so dass u die Gleichung t nicht erfüllt, so ist der Vektor

ungleich dem Vektor

• Damit gilt mit Ws. 1/2 über die Wahl der d, dass

• Der Test wird zwei mal wiederholt, um Fehlerwahrscheinlichkeit 1/4 zu erzielen

Analyse• Vollständigkeit ist 1, da ein ehrlicher Beweis alle Tests

besteht• Korrektheit:

– Falls g,G nicht 0.001-approximativ linear, wird mit Ws. 0.99 verworfen

– Wenn g,G 0.001-approximativ linear sind, ist die Wahrscheinlichkeit eines Fehlers bei der lokalen Dekodierung höchstens 1/20

– Falls g,G 0.01-approximativ linear, aber zugehörige f,F,u,W nicht W=u u erfüllen, wird mit Ws. 2/3 verworfen

– Falls g,G 0.01-approximativ, zugehörige f,G erfüllen f=C(u),F=C(u u), aber u ist nicht erfüllend, dann wird mit Ws. 3/4 verworfen.

• Insgesamt ist die Korrektheit damit mindestens 1-1/4-1/20>2/3

Zusammenfassung

• Insgesamt ist die Vollständigkeit 1, die Korrektheit 2/3

• Zahl der Fragen:– Schritt 1: O(1)– Schritt 2: 15– Schritt 3: 2

• Zufall: In Schritten 2 und 3 ziehen wir insgesamt O(1) Zufallstrings der Länge n, d.h. wir verwenden O(n) Zufallsbits;Der Test in Schritt 1 für U benötigt allerdings O(n2) Zufallsbits

• Damit ist NPµ PCP(O(n2), O(1))

PCP‘s und Approximation

• Wir wollen die wichtigste Anwendung des PCP Theorems betrachten

• Theorem:– NP=PCP(O(log n),O(1))

• Diese besteht darin, zu zeigen, dass es für bestimmte Optimierungsprobleme schwierig ist, diese gut zu approximieren

NP-Optimierungsprobleme• Definition 13.2 [NPO-Probleme]

– Ein NP-Optimierungsproblem P ist gegeben durch eine Menge I von Instanzen (Eingaben), eine Menge L von Lösungen, und zwei Funktionen, die in polynomieller Zeit berechenbar sind:

• feasP: I£ L! {0,1} entscheidet auf x,y, ob y eine zulässige Lösung zu x ist

• costP: I£ L! R gibt die Kosten von y als Lösung zu x an• Es gibt Maximierungs- und Minimierungsprobleme

• Beispiel: Clique– Instanzen sind alle ungerichteten Graphen– Lösungen sind Mengen von Knoten– feasP ist wahr, wenn Knotenmenge y eine Clique in Graph x ist– costP gibt die Größe von y an

• Ein Algorithmus löst ein NP-Optimierungsproblem exakt, wenn er eine optimale Lösung zu jeder Eingabe bestimmt

Approximationsalgorithmen

• Die Entscheidungsversionen vieler NP-Optimierungsprobleme sind NP-vollständig– Clique, MaxCut, VertexCover, SetCover

• Was, wenn wir nicht die beste, sondern nur eine gute Lösung suchen?

• Definition 13.3– Sei P ein NP-Optimierungsproblem– optP(x) sei eine optimale Lösung von P auf x– Eine Lösung y habe Verlustfaktor ,

wenn costP(x,y)· costP(x,optp(x)) für Minimierungsprobleme

– Eine Lösung y habe Verlustfaktor ,wenn costP(x,y)¸ costP(x,optp(x))/ für Maximierungsprobleme

Approximation

• Definition 13.4– Ein Algorithmus, der in polynomieller

Zeit zu einem NP-Optimierungsproblem für beliebige Eingaben x Lösungen mit Verlustfaktor berechnet, heißt-Approximationsalgorithmus für P

Ein Beispiel

• Das Problem Max-3-SAT ist wie folgt gegeben:– Instanzen sind Boolesche Formeln in 3-KNF

Form• Alle Klauseln haben genau 3 Literale

– Zulässige Lösungen sind alle Belegungen der n Variablen

– Die Kosten einer Lösung sind die Anzahl erfüllter Klauseln

– Wir suchen Lösungen, die eine maximale Anzahl von Klauseln erfüllen

• Das Problem ist also ein NPO-Problem und NP-schwierig

Approximation durch Zufall• Approximative Lösung für Max 3-SAT:

– Ziehe alle n Variablen zufällig• Es gebe m Klauseln • Jede Klausel wird mit Wahrscheinlichkeit 1-1/8=7/8

erfüllt• Die erwartete Anzahl erfüllter Klauseln ist somit:

– Sei zi eine Indikatorzufallsvariable, die 1 ist wenn Klausel i erfüllt ist

– Erwartete Anzahl erfüllter Klauseln istE[ zi]= E[zi]=m¢ 7/8

• Wir erhalten somit erwartet eine 8/7 Approximation, denn das Optimum ist höchstens m

Bemerkung

• Dies zeigt, dass in jeder 3-KNF Formel mit m Klauseln (und genau 3 Literalen per Klausel) mindestens 7/8 m Klauseln simultan erfüllbar sind.

Methode des bedingten Erwartungswerts

• Wir wollen den obigen Algorithmus derandomisieren, d.h. einen deterministischen Algorithmus erhalten

• Betrachte die n Zufallswahlen als einen Baum, dessen Blätter mit den strings der Länge n markiert sind

• Der Erwartungswert Ex[i zi(x)] geht über alle Blätter x1,…,xn

• Wir fixieren x1 usw. nacheinander greedy.• Dazu betrachten wir die bedingten Erwartungswerte

Ex [ zi(x)|x1=1] und Ex [ zi(x)|x1=0]• Da 7/8¢ m · Ex[i zi(x)]=

1/2( Ex [ zi(x)|x1=1] + Ex [ zi(x)|x1=0])muss einer von beiden Termen größer als 7/8 m sein

Methode des bedingten Erwartungswerts

• Fixiere x1 so, dass der Erwartungswert über die restlichen Variablen maximal ist und iteriere

• Am Ende erhalten wir eine Lösung mit Kosten mind. 7/8 m

• Allerdings: wie können wir die bedingten Erwartungswerte bestimmen? – Die bedingten Erwartungswerte sind leicht zu

berechnen aufgrund der Linearität des Erwartungswertes: Nach Substitution der Variablen x1,…,xi bleibt eine 3-KNF. 1-Klauseln haben eine Ws. von 1/2, erfüllt zu werden, 2-Klauseln 3/4, 3-Klauseln 7/8.