Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2015/16 / Komplexitätstheorie / PCP Theorem


Inhaltsbereich

PCP Theorem

Plain Text icon pcp.txt — Plain Text, 14 KB (14510 bytes)

Dateiinhalt

Bei IP kann sich der Prover an das Verhalten von V anpassen und
insbesondere je nach Art der bisher gestellten Fragen unterschiedlich
antworten. 

In der Klasse PCP laesst man dies nicht zu; hier muss das
Proververhalten, also der "Beweis" bereits vor Beginn des Protokolls
fest vorliegen. 

Sei Pi ein Wort {0,1}^N. Diesem Wort ordnen wir einen Prover P_Pi wie
folgt zu: auf die Frage q:{0,1}* antwortet der Prover mit dem q-ten
Bit von Pi. Man beachte, dass selbst bei polynomialer Laufzeit des
Verifiers der "Beweis" durchaus exponentielle Laenge haben kann. Eine
Laenge der Form exp(exp(n)) macht allerdings keinen Sinn mehr, da dann
nur ein echtes Anfangsstueck des Beweis ueberhaupt inspiziert werden
koennte. 

Definition: Ein Problem A ist in der Klasse PCP, wenn es einen
Verifier (polynomial zeitbeschraenkte randomisierte Orakel
Turingmaschine) gibt, sodass 

x:A ==> es ex Beweis Pi = Pi_x sodass Pr(V,P_Pi akzeptiert x) = 1
~x:A => fuer alle Beweise Pi ist Pr(V,P_Pi akzeptiert x) <= 1/2. 

Natuerlich ist IP enthalten in PCP. Wir codieren einfach das Verhalten
des erfolgreichen Provers in einen Beweis, also eine Tabelle in der
alle Verhaltensmuster des Provers abgespeichert sind. Kann dagegen der
Verifier alle schlechten Prover erkennen, so auch insbesondere
diejenigen von der Form P_Pi.

Die umgekehrte Richtung gilt nicht in offensichtlicher Weise und ist
auch unwahrscheinlich, da man zeigen kann

Theorem: PCP = NEXP. 

Fuer die Anwendungen wichtig sind nun Einschraenkungen von PCP
hinsichtlich der Zahl der Fragen an den Beweis und der Zahl der
verwendeten Zufallsbits:

Definition PCP(r(n), q(n)) ist die Klasse der Probleme, fuer die es
einen PCP Verifier gibt, der bei Eingabe der Laenge n
O(r(n))-Zufallsbits benutzt und O(q(n))-Fragen an den Prover, also den
Beweis stellt. 

Theorem [PCP-Theorem, Arora et al]: NP = PCP(log(n), 1)

Wir werden hier das schwaechere folgende Resultat beweisen. 

Theorem: NP <= PCP(poly(n), 1)

Man kann also einen Beweisbegriff fuer SAT finden, derart dass gilt:
Ein korrekter Beweis wird immer akzeptiert; falsche Beweise werden mit
W. >=1/2 erkannt; hierbei wird nur eine feste Zahl von Bits des Beweis
besichtigt. Die Anzahl ist also unabhaengig von der
Eingabegroesse. Allerdings wird je nach Wahl der Zufallsentscheidungen
eine andere Auswahl der Bits abgeprueft, sodass im Prinzip jedes Bit
drankommen koennte.

Der Beweis folgt dem Buch von Motwani (Randomized algorithms). 

Gegeben sei eine 3KNF mit m Klauseln und n Variablen x1..xn. Wir
codieren diese wie folgt in ein Polynom vom Grad 3 ueber Z/2Z:

[xi]  = 1-xi
[~xi] = xi
[abc] = [a][b][c]
[c1&...&cm] = sum_i [c_i]

Beob: Sei A eine Belegung und a der Vektor definiert durch TRUE->1,
FALSE->0. Wenn C(A)=TRUE, dann ist [C](a) = 0. Leider kann es aber
passieren, dass [C](a) = 0, obwohl C(A)=FALSE. Dies ist
naemlich genau dann der Fall, wenn die Zahl der unerfuellten Klauseln
gerade ist. 

Um dem entgegenzuwirken, verwenden wir wieder den Zufall: Wir lassen r
=(r_j) einen uniform verteilten Zufallsvektor der Laenge m (Anzahl der
Klauseln) sein und definieren das Zufallspolynom

f(x) = sum r_i*[c_i]

wir summieren also nur ueber die ausgelosten Klauseln. 

Wir brauchen nun ein Lemma der linearen Algebra: 

Lemma: Sei V ein (Z/2Z)-Vektorraum und h : (Z/2Z)^n -> V eine lineare
Abbildung und h =/= 0. Dann ist Pr(h(x)=/=0) >= 1/2 fuer x uniform aus
(Z/2Z)^n gezogen.

Beweis: Der Kern von h ist ein Vektorraum von Dimension <= n-1. Somit
enthaelt er maximal 2^(n-1) Vektoren und die anderen 2^(n-1) sind im
Nicht-Kern. Die Wahrscheinlichkeit, einen von denen zu treffen ist
somit >= 1/2. 

Korollar: Sei h : (Z/2Z)^m * (Z/2Z)^n -> V bilineare Abbildung
=/=0. Pr(h(x,y)=/=0) >= 1/4. 

Beweis: Wir betrachten zunaechst die Abbildung curry(h) : (Z/2Z)^m ->
Lin((Z/2Z)^n,V) in den VR der linearen Abbildungen. Da curry(h)=/=0,
ist die W, einen Vektor x zu finden mit curry(h)(x)=/=0 mindestens
1/2. Dafuer dass nun auch h(x,y) = curry(h)(x)(y)=/=0 wird, ist die W
dann 1/4. 

Nach diesem Exkurs in die Lineare Algebra wenden wir uns nunmehr
wieder dem Zufallspolynom f zu. Es gilt: 


Lemma: C(A) = TRUE => f(a)=0, C(A)=FALSE => Pr(f(a)=0) <= 1/2. 
Beweis: Sei c der Vektor (von Dimension m) der [c_i](a). Die lineare
Abbildung h(r) = c.r (Skalarprodukt) ist verschieden von Null, das
Resultat folgt also mit dem Lemma. Die W. ist hier sogar exakt = 1/2,
da der Kern hier die Dim. n-1 hat. 

Definition: Sei a ein Vektor der Dimension n (Zahl der Variablen),
also eine Zuweisung. Wir setzen 


G^1_a(z1..zn) = sum_i a_i.z_i
G^2_a(z11..znn) = sum_i sum_j.a_i.a_j.z_ij
G^3_a(z111..znnn) = sum_i sum_j sum_k.a_i.a_j.a_k.z_ijk

Hier hat also G^i_a insgesamt n^i Variablen!

Der Verifier geht nun wie folgt vor: zunaechst bestimmt er einen
Zufallsvektor r wie oben und bildet dann f(x1..xn) wie oben. 

Nunmehr schreibt er f(x) in der Form 

f(x) = alpha + sum_(i:S1) x_i + sum_ij_S2 x_i.x_j + sum_ijk:S3
x_i.x_j.x_k. 

indem die Terme vom Grad 0,1,2,3 jeweils zusammengefasst
werden. Hierbei ist alpha:Z/2Z und S1 eine Teilmenge von {1..n}, S2
eine Teilmenge von {1..n}^2 und S3 eine Teilmenge von {1..n}^3.

Ist nun a eine Variablenbelegung, so ist f(a) = alpha + G^1_a(S1) +
G^2_a(S2) + G^3_a(S3), wobei natuerlich jetzt beispielsweise S1 diejenige
Belegung ist, die fuer zi 0 bzw 1 einsetzt je nachdem ob i:S1 oder
nicht. 

Man kann also als "Beweis" die drei Funktionen G^1_a, G^2_a, G^3_a nehmen,
die zu einer erfuellenden Belegung gehoeren und dann drei 0/1 Abfragen
taetigen, naemlich die Werte G^1_a(S1), G^2_a(S2), G^3_a(S3). Ist die
Summe dieser drei plus alpha = 0, so ist mit W <= 1/2 die Formel
unerfuellbar. 

Das alleine reicht noch nicht aus, denn der Prover koennte diese
Funktionen auch anders waehlen, insbesondere nicht von der Bauart
G^1_a,G^2_a,G^3_a fuer eine feste Belegung a. Dies gilt es nun durch
weitere (aber konstant viele) Abfragen auszuschliessen.

Wir werden zunaechst durch einige Tests der Form G^i(x+y) =?= G^i(x) +
G^i(y) sicherstellen, dass die G^i lineare Funktionen sind. Da man
natuerlich nicht alle Wertepaare x,y abpruefen kann, wird man so nur
eine Aussage der Form "der Anteil derjenigen x,y fuer die gilt
G^i(x+y)=G^i(x)+G^i(y) ist hoch" erhalten. Dass man mit solch einer
Information noch etwas anfangen kann, ist Gegenstand des folgenden
Lemmas aus der Codierungstheorie. 

Lemma (Blum-Luby-Rubinfeld, Coppersmith): Sei delta<1/6 und sei f :
(Z/2Z)^n -> Z/2Z eine Funktion derart, dass Pr(f(x+y) = f(x)+f(y)) >=
1-delta fuer x,y unabhaengig und uniform verteilt.  

Dann existiert eine lineare Funktion g, sodass Pr(f(x) = g(x)) >=
1-3*delta. 

Darueberhinaus gilt g(x) = f(x+y)-f(y) mit W >= 1-2delta fuer festes x
und zufaelliges y.


Beweis: Fixieren wir x. Fuer variierendes y kann f(x+y)-f(y) entweder
0 oder 1 sein. Sei c derjenige Wert, der bei der Mehrheit der y
angenommen wird. Wir setzen dann g(x) = c. 

Wir werden nun zeigen, dass diese Mehrheit ueberwaeltigend ist,
naemlich 1 - 2*delta und dass g ausserdem eine lineare Funktion ist. 

1) Pr(g(x) = f(x+y)-f(y)) >= 1-2*delta fuer festes x und uniform
   verteiltes y. 

Sei p die W dass f(x+y)-f(y) = g(x). Fuer unabhaengige y1, y2 sind sowohl
x+y1,y2 als auch x+y2,y1 jeweils unabhaengig. Daher gilt 

Pr(f(x+y1+y2)=f(x+y1)+f(y2)) >= 1-delta
Pr(f(x+y1+y2)=f(x+y2)+f(y1)) >= 1-delta

Also ist 

Pr(f(x+y1)-f(y1) = f(x+y2)-f(y2)) = 
Pr(f(x+y1)+f(y2) = f(x+y2)+f(y1)) >= 1-2*delta

Die Wahrscheinlichkeit hierfuer ist aber andererseits gleich p^2 +
(1-p)^2. Es folgt p >= 1-2*delta mit elementarer Kurvendiskussion: 
p^2+(1-p)^2 = 2p^2-2p+1 = 2((p- 1/2)^2 + 3/4). Minimum bei p=1/2: 3/2 
       Also p^2 + (1-p)^2 <= p fuer p=1/2..1


2) Pr(g(x) = f(x)) >= 1 - 3*delta. 
   Waehle x gleichverteilt und dann y unabhaengig und
   gleichverteilt. 
   Pr(g(x) = f(x)) >= Pr(g(x) = f(x+y)-f(y) & f(x+y)=f(x)+f(y)) >=
   1 - 2*delta-delta = 1 - 3*delta. 

3) g ist linear. Seien u,v gegeben. Nach 1) muss es ein y geben (hier
   geht die Annahme delta<1/6 ein), sodass 
   g(u+v) = f(u+v+y) - f(y)
   g(u)   = f(u+v+y) - f(v+y)
   g(v)   = f(v+y)   - f(y). 
   Es folgt g(u+v) = g(u) + g(v).                            QED 

Des weiteren kommt nun ein Trick zum Einsatz, der unter der
Bezeichnung "random self correction" bekannt ist. Naemlich kann man
statt f(x) auch f(x+y)-f(y) betrachten und diese Funktion ist mit W >=
1-3delta gleich der linearen Funktion g. 

Das heisst also, dass wenn immer wir in der Zukunft uns fuer einen
f-Wert interessieren, wir in Wirklichkeit f(x+y)-f(y) auswerten fuer
ein zufaelliges y. 

Fassen wir zusammen. Gegeben sind die drei Funktionen G^1, G^2,
G^3. Zunaechst fuehren wir mit jeder der drei Funktionen eine
bestimmte Zahl von Linearitaetstests der Form f(x+y) =?= f(x)+f(y)
durch. Werden diese alle bestanden, so ist die Wahrscheinlichkeit,
dass der Anteil der Linearitaetsverletzungen groesser ist als delta
(fuer fest gewaehltes kleines delta, z.B delta=0,0001) beliebig gering. 

Wir koennen also mit hoher W davon ausgehen, dass die Bedingungen des
Lemmas erfuellt sind. Es existieren also ueberall lineare Funktionen
G^1', G^2', G^3', deren Werte uns zwar nicht direkt zugaenglich sind,
aber doch mit hoher (1-3delta) W. durch random self correction abgerufen
werden koennen. 

Es ist wichtig, dass wir nicht mit G^1, G^2, G^3 selbst
weiterarbeiten, da diese ja zum Beispiel an wenigen Stellen von einer
linearen Funktion abweichen koennen und andererseits aber die
folgenden Tests, mit denen festgestellt wird, ob die G's alle von
derselben Belegung herruehren, die Linearitaet voraussetzen. Man
koennte also diesen jetzt zu formulierenden Test leicht aufs Kreuz
legen, wenn man an ein paar Stellen die Linearitaet verletzen
duerfte. 

Arbeiten wir dagegen mit G^i', so duerfen wir davon ausgehen, dass die
Funktionen wirklich linear sind, das einzige was passiert, ist, dass
jedes einzelne Abrufen eines Funktionswertes die Gesamtfehlerw. um
3delta erhoeht. 

Es bleibt also abzupruefen, ob drei vorgelegte lineare Funktionen G^1,
G^2, G^3 von der Form G^1_a, G^2_a, G^3_a fuer ein festes a sind. 

Hierzu bemerken wir, dass fuer beliebige Vektoren r und s gilt 

G^1_a(r) * G^1_a(s) = G^2_a(t) wobei tij = ri*sj (wir schreiben dafuer kurz t = r o s)

und desweiteren fuer beliebige r,s,t

G^1_a(r) * G^1_a(s) * G^1_a(t) = G^3(u) wobei uijk = ri*sj*tk. ( wir schreiben dafuer kurz u = r o s o t)

Man hat also eine bilineare Abbildung 

h(r,s) = G^1_a(r) * G^1_a(s) - G^2_a(t) wobei tij = ri*sj 

die Null sein sollte. Ist sie von Null verschieden, so bemerkt man das
aber nach dem Lineare Algebra Lemma schon durch einen einzigen Test
mit W. 1/4, somit durch ein paar mehr Tests auf beliebige
Genauigkeit. Analog verfaehrt man mit der trilinearen Funktion

k(r,s,t) = G^1_a(r) * G^1_a(s) * G^1_a(t) - G^3(u) wobei uijk = ri*sj*tk. 

Fassen wir nochmal zusammen. Gegeben ist eine 3KNF C = /\_i c_i mit n
Variablen und m Klauseln. Wir codieren jede Klausel c_i als Polynom
[c_i] vom Grad 3, z.B. [x|~y|z] = (1-x)y(1-z). 

Nun waehlen wir einen Zufallsvektor r in (Z/2Z)^m und bilden das
Polynom f = sum_i r_i*[c_i] in der Form 

alpha + sum_{i:S1}xi + sum_{(i,j):S2}xixj + sum_{(i,j,k):S3}xixjxk

Ist a eine erfuellende Belegung, so ist f(a)=0. Ist dagegen a keine
erfuellende Belegung, so ist Pr(f(a)=/=0) >= 1/2.  

Wir erwarten nun einen Beweis in der Form dreier Funktionen G^1, G^2,
G^3. 

Zunaechst pruefen wir an mehreren unabhaengigen Stellen, ob die G^i
linear sind. Schlaegt auch nur einer dieser oder der folgenden Tests
fehl, so verwerfen wir sofort. 

Von hier an ersetzen wir G^i durch G^i(x+y)-G^i(y) wobei y ein bei
jedem Abruf neu zu waehlender Zufallsvektor ist. Wir kennzeichnen
diese neue Funktion nicht eigens notationell. 

Nun sehen wir mehrfach, ob G^1(r)G^1(s) = G^2(r o s) und
G^1(r)G^1(s)G^1(t) = G^3(r o s o t) fuer jeweils frisch zu waehlende
Zufallsvektoren r,s,t. 

Schliesslich waehlen wir mehrfach Zufallsvektoren r und bilden jeweils
das zugehoerige Polynom f und die Indexmengen S1, S2, S3. Jeweils
pruefen wir, ob alpha + G^1(S1) + G^2(S2) + G^3(S3) = 0. 

Wurden alle Tests erfolgreich passiert, so wird der Beweis akzeptiert,
ansonsten verworfen. Hierbei wurden die Funktionen G^i an einer festen
Zahl von Malen ausgewertet, was jeweils ein Bit zurueckliefert. Somit
wurde nur eine konstante Zahl von Bits inspiziert. Die Anzahl der vom
Verifier zum Prover kommunizierten Bits ist natuerlich hoeher,
naemlich polynomiell. 

Im richtigen PCP Theorem allerdings kann diese immerhin auf O(log(n))
gedrueckt werden. Das richtige PCP Theorem hat interessante
Anwendungen auf Nichtapproximierbarkeitsresultate. 


Definition (MAXCLIQUE-APPROX, kurc MCA): Gegeben ein ungerichteter Graph 
G=(V,E). Man berechne eine Clique K in G, die mindestens halb so gross wie eine maximal grosse Clique in G ist. 



Theorem:  Falls P=/=NP, so kann keine polynomielle Implementierung von MCA existieren. 

D.h. unter der Annahme P=/=NP kann MAXCLIQUE nicht effizient
approximiert werden.

Beweis: (unter Verwendung des PCP-Theorems!) 

Sei V ein PCP(log(n),1)-Verifier fuer SAT und eine Eingabe-KNF f der Laenge n=|f| gegeben. Wir nehmen der Einfachheit halber an, dass V immer dieselbe Zahl von Zufallsbits verwendet und dass die Anzahl der Fragen auch immer dieselbe ist. Ein Transcript (von V auf f) ist eine Folge (r,q1,a1,q2,a2,..,qt,at), wobei r eine Wahl der Zufallsentscheidungen und qi, ai eine Folge von Fragen und Antworten ist und die eine *akzeptierende* Berechnung repraesentiert. 
 Man beachte, dass t und |ai| konstant sind, |r|=O(log(n)), |qi|=poly(n). 

Zwei Transcripts (r,q1,a1,q2,a2,..,qt,at) und  (r',q1',a1',q2',a2',..,qt',at')
sind konsistent, wenn fuer alle i gilt: qi=qi' => ai=ai'

Wir bilden nun den Graphen G, dessen Knoten die Transcripts sind und in dem konsistente Transcripts durch eine Kante verbunden sind. 

In einem Transcript koennen die qi mithilfe von V aus r und den ai
rekonstruiert werden, daher ist die Knotenzahl von G durch
2^{O(log(n)}=poly(n) beschraenkt. 

Sei jetzt d=O(log(n)) die Zahl der Zufallsbits, also |r|. 
Wir behaupten nun: Ist f:SAT, so existiert in G eine Clique der Groesse mindestens 2/3 d und falls f nicht in SAT, so ist die groesste Clique hoechstens 1/3 d. 

Ein "Beweis", der V mit W. >=2/3 akzeptieren laesst, liefert
natuerlich eine entsprechende Clique und umgekehrt liefert jede Clique
der Groesse g einen Beweis, der V mit W. g/d akzeptieren laesst. Die
beiden Faelle lassen sich nun aber durch einen Aufruf an MCA
voneinander trennen.


Artikelaktionen


Funktionsleiste