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.