Untere Schranke fuer die Paritaetsfunktion nach Razborov und Smolensky Der Aufschrieb orientiert sich am Buch von Schoening (Perlen der Th.Inf.) und am Buch "The Probabilistic Method" von Alon und Spencer. Beide scheinen allerdings Schnitzer zu enthalten, die hier eliminiert sind. Dafuer natuerlich andere eingebaut :-) Zur Ascii Notation: *) x:A steht fuer x Element von A *) x<=y steht fuer x kleiner gleich y, aber je nach Zshg auch x Teilmenge von y. Ebenso >=. *) x_1 steht fuer x Subskript 1, x^n steht fuer x Superskript (hoch) n *) Bisweilen schreibt man x1 oder xi statt x_1, bzw. x_i *) Mit (...) oder {...} koennen Sub- und Superskripte geklammert werden, also z.B. x_(2k+1) steht fuer x unten 2k+1 *) sum steht fuer das Summenzeichen (Sigma) und prod fuer das Produktzeichen (Pi). *) xs, ys etc steht (in Haskell Tradition) fuer x-vektor, y-vektor, also z.B. (x_1,...,x_n) (y_1,...,y_m). *) & steht fuer "geschnitten mit", u steht fuer "vereinigt mit". Wir identifizieren 0=ff, 1=tt. Def. (PARITY): Fuer n:N ist par_n:{0,1}^n->{0,1} definiert durch par_n(x1,...,xn) = x1+...+xn mod 2. Die Familie der par_n heisst Paritaetsfunktion und wird kurz mit PARITY bezeichnet. Die Wahrheitstafel fuer par_n hat genauso viele 1en wie 0en. 0000 0 0001 1 0010 1 0011 0 0100 1 0101 0 0110 0 0111 1 ... Wir praesentieren hier das Resultat von Furst-Saxe-Sipser (1984), dass die Paritaetsfunktion nicht durch Boole'sche Schaltkreise polynomialer Groesse und konstanter Tiefe berechnet werden kann. Wir verwenden allerdings die methodisch interessantere Beweistechnik von Razborov und Smolensky, welche noch weitere Anwendungen hat. Im Gegensatz zu diesem Resultat gibt es Boolesche Schaltkreise konstanter Tiefe, aber exponentieller Groesse, die PARITY berechnen (DNF) und man kann PARITY auch mit polynomiell grossen Schaltkreisen logarithmischer Tiefe berechnen. Boole'sche Schaltkreise bestehen hier aus UND, ODER Gattern beliebiger Stelligkeit (fan-in), sowie Negation. Diese kann man allerdings mit de Morgan nach ganz unten verschieben, sodass wir einen Schaltkreis aus UND, ODER Gattern aufgebaut denken koennen, wobei aber an den Eingaengen negierte und nichtnegierte Variablen stehen. Ein Schaltkreis fuer eine n-stellige Funktion hat also 2n Eingaenge. Aufeinanderfolgende UND Gatter kann man verschmelzen und gleiches fuer ODER Gatter. So kann man davon ausgehen, dass UND und ODER Gatter abwechselnd in Schichten auftreten. Mithilfe des Distributivgesetzes kann eine UND-Schicht mit einer ODER Schicht vertauscht werden und somit (nach Verschmelzen) die Tiefe reduziert werden. Abhaengig vom fanin der beteiligten Gatter erhoeht sich aber deren Anzahl. Genauer gesagt, wird ein UND an dem d ODERs mit fanin je c dranhaengen zu einem ODER mit fanin c^d, an dem UNDs mit fanin je d dranhaengen: /\_i:d \/_j:c l_ij = \/_f:c^d /\_i:d l_{i,f(i)} Def.: Eine Schaltkreisfamilie S_n, n:N berechnet PARITY, wenn jeder Schaltkreis S_n die Funktion par_n berechnet. Er hat polynomielle Groesse, wenn es ein Polynom p gibt, sodass |S_n|<=p(n) fuer alle n. Sie hat Tiefe f(n), wenn die Tiefe von S_n durch f(n) beschraenkt ist. Def (AC0): Die Klasse AC0 umfasst alle Familien von Booleschen Funktionen (also Sprachen ueber dem Alphabet {0,1}), welche durch Schaltkreisfamilien polynomieller Groesse und konstanter Tiefe (also Tiefe f(n)=c fuer ein festes c) berechnet werden koennen. Def (ACk): Die Klasse ACk umfasst alle Familien von Booleschen Funktionen (also Sprachen ueber dem Alphabet {0,1}), welche durch Schaltkreisfamilien polynomieller Groesse und Tiefe O(log^k(n)) berechnet werden koennen. Fuer die Klasse AC1 ist die Tiefenbeschraenkung dann logarithmisch. Def (NCk): Die Klassen NCk sind wie ACk definiert, zusaetzlich ist der fanin der beteiligten Gatter konstant (oBdA auf zwei beschraenkt). Satz: ACk ist in NC(k+1) enthalten. Beweis: Der fanin eines Gatters in einem (durch p(n) groessenbeschraenkten) ACk Schaltkreis ist hoechstens 2n+p(n). Durch einen Binaerbaum der Hoehe log(2n+p(n))=O(log(n)) aus Gattern von fanin 2 kann man so ein Gatter implementieren. Satz: PARITY ist in NC1 Beweis: Man baut zunaechst einen als Binaerbaum organisierten Schaltkreis aus EXOR Gattern mit fanin 2. Diese kann man dann jeweils durch UND-ODER-Negation implementieren. Natuerlich ist PARITY dann erst recht in AC1, da die fanin Beschraenkung dort wegfaellt. Satz: Ist L in ACk und existiert zudem ein Algorithmus, der fuer jedes n in polynomieller (in n) Zeit einen entsprechenden Schaltkreis S_n berechnet (die Schaltkreisfamilie ist also uniform), so ist L in P (Polynomialzeit). Beweis: Zu gegebener Eingabe x der Laenge n berechnet man zunaechst den Schaltkreis S_n und wertet ihn dann auf x aus. Das geht in polynomieller Zeit, da die Zahl der Gatter polynomiell ist. Die Beschraenkung auf polylogarithmische Tiefe wurde hier gar nicht genutzt. Man deutet die Klassen ACk und NCk fuer kleines k als Klasse der effizient parallelisierbaren Sprachen in P, da ja z.B. eine NC2 Schaltkreisfamilie bei unbegrenzter Prozessorzahl in Zeit log^2(n) ausgewertet werden kann. Natuerlich ist es wiederum offen, ob die Vereinigung der NCk (oder der ACk was dasselbe ist) ganz P erfasst. Wir zeigen jetzt Satz: PARITY ist nicht in AC0. Die Bedeutung dieses Ergebnisses liegt darin, dass es zum einen eine nichttriviale untere Schranke beinhaltet, die auch irgendwie polynomiell von exponentiell trennt: bei konstanter Tiefe geht es ja exponentiell mit DNF. Man kann sie also als Schritt auf dem Weg zur Trennung von P und NP deuten. Zum anderen sind die verwendeten Beweismethoden neuartig und interessant. Der hier praesentierte Beweis geht auf Razborov und Smolensky zurueck. Man zeigt, dass fuer jede AC0 Funktion f eine Familie von Polynomen p_n in n Variablen existiert, so dass Pr_x(p_n(x)=f(x)) >= 0,9 und gleichzeitig deg(p_n) = o(sqrt(n)). Auf der anderen Seite zeigt man dann, dass die Paritaetsfunktion keine solche Approximation gestattet. Zunaechst betrachten wir die exakte Repraesentation von Schaltkreisen durch Polynome: [x] = x [~x] = 1-x [f1 /\ ... /\ fn] = [f1]*...*[fn] [f1 \/ ... \/ fn] = 1 - (1-[f1])*...*(1-[fn]) Problem dabei ist, dass der Grad dieser Polynome sehr gross wird. Auf der anderen Seite repraesentieren diese Polynome einen gegebenen Schaltkreis nicht nur auf 90% der Punkte, sondern auf allen. Wir werden jetzt zeigen, wie man die ODER Funktion (und damit per de-Morgan natuerlich auch die UND Funktion und alle anderen) durch ein Polynom moderaten Grades approximieren kann. Betrachten wir ein m-stelliges ODER x_1 \/ ... \/ x_m. Wir setzen l = log m + 2 und definieren wie folgt eine Familie von Teilmengen {1..m} = S_0 >= S_1 >= ... >= S_l Ist S_i <= {1..m} schon gewaehlt, so waehlt man S_(i+1) <= S_i so, dass jedes Element j:S_i mit W. 1/2 erhalten bleibt. Es gilt also Pr(j:S_(i+1) | j:S_i) = 1/2 Fuer jedes i bilden wir jetzt das Polynom q_i = sum_(j:S_i) x_j Sind alle x_j Null, so ist natuerlich auch q_i Null fuer jedes i. Ist genau eines der x_j mit j:S_i gleich 1, so wird auch q_i gleich 1. Sind dagegen mehrere x_j in einem S_i gleich 1, so ergibt sich ein anderer Wert. Man bildet nun q = 1 - (1-q_0)*(1-q_1)*...*(1-q_l) Es gilt folgendes: Sind alle x_j gleich 0, so ist auch q=0. Gilt fuer mindestens ein i, dass genau eines der x_j fuer j:S_i gleich 1 ist, so ist q=1. Wir wollen jetzt sehen, dass in dem Falle, dass x_1\/...\/x_m = 1 ist, dieses Ereignis mit W. >= 1/2 eintritt. Satz: Es sei T eine nichtleere Teilmenge von {1..m} und S_0,...,S_l die obige durch einen Zufallsprozess definierte Folge von Teilmengen. Die W. dafuer dass |T & S_i| = 1 fuer mindestens ein i ist >= 1/2. Beweis: Es ist Pr(|S_l & T| > 1) <= Pr(|S_l & T| >= 1) <= m*2^{-l} = 1/4 Beachte: l = log m + 2. Mit W. >= 3/4 ist also |S_l & T| <= 1. Wenn nun nicht |T|=1 ist, was ja auf jeden Fall guenstig waere, koennen wir also 1 1 und |S_i & T| <= 1. Die W., dass nunmehr |S_i & T| = 1, ergibt sich zu t*2^(-t) / (2^(-t)+t*2^(-t)) = t/(1+t) >= 2/3. Verstaendnishilfen: 1) Bedingte Wahrscheinlichkeit: Pr("=1" | "<=1") = Pr("=1") / Pr("<=1")). 2) "=1" t-1 kommen weg, einer bleibt. Bernoulli mit n=t,k=1,p=1/2 3) "<=1" t-1 kommen weg, s.o., oder alle kommen weg. Der guenstige Fall ergibt sich also mit W. >= 3/4 * 2/3 = 1/2 QED Fassen wir zusammen: ist x_1 \/ ... \/ x_m = 0, so ist q(xs)=0. ist hingegen x1 \/ ... \/ x_m = 1, so ist Pr(q(xs)=1) >= 1/2. Um nun die W. zu erhoehen, bilden wir Zufallspolynome q_1,...,q_t genauso wie q aber mit jeweils frischen Zufallszahlen und konstruieren q' = 1 - (1-q_1)*...*(1-q_t) Ist x_1\/...\/x_m=1, so ist q'(xs)=1 mit W. >= 1 - 2^(-t). Der Grad von q' ist O(t*log(m)). (NB: Der Grad von q_j ist O(l)=O(log m)). D.h. also, das sich fuer eine W. >= 1-epsilon ein Grad von O(log(1/epsilon)*log(m)) ergibt. Haben wir nun einen Schaltkreis der Groesse s und der Tiefe t und eine vorgeschriebene Fehlerschranke epsilon, so koennen wir jedes Gatter durch ein entsprechendes Polynom mit Fehlerwahrscheinlichkeit epsilon/s ersetzen, sodass dann mit W. >= 1-epsilon alle Gatter das Richtige tun und somit das richtige Endergebnis geliefert wird. (NB (1-a)(1-b)=1-(a+b)+ab) >= 1-(a+b). Daher (1-x)^n >= 1-nx, daher (1-epsilon/s)^s >= 1-epsilon) Der Grad des entstehenden Polynoms ergibt sich dann zu O((log(s/epsilon)*log(s))^t) = (log(n) * log(1/epsilon))^O(t) = log(n)^O(1) wenn s = poly(n) und t, epsilon konstant. Wir fixieren nunmehr epsilon = 1/10. Wir setzen B fuer die Menge der Belegungen der x_i, also |B|=2^n und Z fuer die Menge der Zufallsentscheidungen. Es ist egal, wie gross Z ist. Wir definieren eine Relation F<=B*Z durch F(b,z) <==> das sich fuer z ergebende feste Polynom liefert bei Eingabe b das richtige Ergebnis. Fuer jedes b ist der Anteil der z mit F(b,z) >= 90%. Die Zahl der Paare (b,z):F ist also |B| * 0,9 * |Z|. Waere jetzt fuer jedes z:Z der Anteil der b mit F(b,z) echt kleiner als 90%, so waere die Zahl dieser Paare < |Z|*0,9*|B|. Nachdem das aber nicht der Fall ist, muss es eine feste Zufallsentscheidung z geben, sodass der Anteil der b mit F(b,z) mindestens 90% ist. Dieses z wird jetzt festverdrahtet und wir erhalten also ein Polynom vom Grade log(n)^O(1) welches fuer 90% der Belegungen funktioniert. Insbesondere gibt es also ein Polynom vom Grad sqrt(n)/2, welches fuer 90% der Belegungen und hinreichend grosse n funktioniert. Dies deshalb, weil sqrt(n) staerker waechst als log(n)^t fuer jedes t. Wir zeigen jetzt, dass fuer die Paritaetsfunktion kein solches Polynom existiert. Hierzu fixieren wir hinreichend grosses n und ein Polynom q' in x_1 .. x_n vom Grade sqrt(n)/2, sowie eine Teilmenge S' <= 2^n, mit |S'|=0,9*2^n, derart dass q'(xs) = par_n(xs) fuer alle xs:S'. Wir gehen nunmehr zur Fourier - Repraesentation der Wahrheitswerte ueber, welche tt durch -1 und ff durch 1 repraesentiert. Diese hat hier den Vorteil, dass die Paritaetsfunktion durch das Polynom x_1 * ... * x_n repraesentiert ist. Durch eine lineare Transformation koennen wir unser q' zu einem Polynom q umbauen, welches die Paritaetsfunktion auf 90% der Eingaben im Sinne von Fourier repraesentiert. q(x1,...,xn) = 1 - 2*q'((1-x_1)/2,...,(1-x_n)/2) Ebenso setzen wir S = {(x_1,...,x_n) : {-1,1}^n | ((1-x_1)/2,...,(1-x_n)/2):S'} und es gilt dann q(xs) = x_1*...*x_n fuer alle xs:S (*) Wegen 1^2=(-1)^2=1 koennen wir o.B.d.A. voraussetzen, dass q multilinear ist. Einen Teilausdruck x_i*x_i kann man ja einfach streichen, ohne die Eigenschaft (*) zu verletzen. Wir betrachten jetzt den Vektorraum V der multilinearen Polynome vom Grad hoechstens (n+sqrt(n))/2. Er wird aufgespannt von den Monomen prod_{i:U}x_i fuer Teilmengen U <= {1..n} mit |U|<=(n+sqrt(n))/2. Es gilt daher /n\ dim(V) = sum_{i=1..(n+sqrt(n))/2} ( ) <= 0,88*2^n \i/ Letztere Abschaetzung kann man mit der Stirling - Approximation beweisen. Mithilfe des hypothetischen Polynoms q werden wir nun fuer jedes s:S ein Polynom h(s) : V konstruieren, sodass die Menge der h(s) linear unabhaengig ist. Das waere dann ein Widerspruch, da ja deren Zahl 0,9*2^n > 0,88*2^n ist. Gegeben s=(s_1,...,s_n):S so definieren wir zunaechst einmal k_s derart, dass | 1, falls xs=s, also x_i=s_i fuer i=1..n k_s(x_1,...,x_n) = < (**) | 0, falls xs:S und xs =/= s Es interessiert eigentlich gar nicht, wie dieses Polynom aussieht. Wir koennen es zum Beispiel dadurch erhalten, dass wir die logische Formel x <=> s als DNF schreiben, exakt codieren und dann in die Fourier-Repraesentation umrechnen. Wir koennen nun k_s ausmultiplizieren und unter Beibehaltung der Eigenschaft (**) alle Quadrate streichen, sodass wir o.B.d.A voraussetzen duerfen, dass k_s multilinear ist. Des weiteren --- und das ist der entscheidende Trick --- koennen wir jedes Monom prod_(i:U)x_i, wobei |U|>n/2 ersetzen durch q(xs)*prod(i:{1..n}\U)x_i. Durch diese Prozedur kann der Grad von k_s auf (n+sqrt(n))/2 abgesenkt werden. Schauen wir noch einmal, warum diese Ersetzung funktioniert: Fuer alle xs:S gilt ja: q(xs) = prod xs. Also prod(i:{1..n}\U)x_i * q(xs) = prod(i:{1..n}\U)x_i * prod(xs) = prod(i:U)x_i. Die k_s sind also nach diesen Vereinfachungsschritten, die wir o.B.d.A. als durchgefuehrt voraussetzen, in V enthalten. Wir argumentieren nun, dass die k_s linear unabhaengig sind: Wenn sum_(s:S) lambda_s*k_s = 0, so gilt fuer jedes s_0:S insbesondere 0 = (sum_(s:S) lambda_s*k_s)(s_0) = lambda_(s_0). Also sind alle lambda_s Null. Da aber |S| = 0,9*2^n > dim(V) liefert dies den gewuenschten Widerspruch. QED In den urspruenglichen Arbeiten von Smolensky und Razborov wurde mit dem Koerper GF(3) = Z/2Z gearbeitet. Es aendert sich an und fuer sich gar nichts (man muss natuerlich aufpassen, dass man nirgendwo durch 3 dividiert hat!). Dafuer ergibt sich aber der Bonuseffekt, dass ueber GF(3) auch die mod3 Funktion, also mod3(x1,...,xn) = 1, gdw die Zahl der gesetzten Bits in x1..xn kein Vielfaches von 3 ist, als Polynom von niedrigem Grad repraesentiert werden kann und das sogar exakt. Man setzt einfach mod3 = (x1+...+xn)^2 Daraus folgt dann, dass die Paritaetsfunktion auch nicht unter Zuhilfenahme solcher mod3 Gatter von beliebigem Fanin repraesentiert werden kann (bei konstanter Tiefe und polynomieller Groesse versteht sich). Kurz: PARITY notin AC0[mod3].