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 geben einen alternativen Beweis dafuer, dass die Paritaetsfunktion nicht in AC0 ist, der auf Razborov und Smolensky zurueckgeht. Hier zeigt man, 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 wiederholen 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 (O(p(p(...p(n)...)) mit t (Tiefe des Schaltkreises) Stueck hintereinandergeschrieben.) 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 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 in 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_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 in 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: Wir betrachten zunaechst den Fall, dass |T & S_l|1 ist. Die W. dafuer ist <= die W. dafuer dass |T & S_l| >= 1 Nehmen wir also an, dass mindestens ein x_j = 1 ist. Zunaechst einmal koennte es passieren, dass |S_l & T| > 1 ist. Die W. dafuer kann man so abschaetzen: Pr(|S_l & T| > 1) <= Pr(|S_l & T| >= 1) <= n*2^l = 1/4 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. 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)). 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. Der Grad des entstehenden Polynoms ergibt sich zu O((log(s/epsilon)*log(s))^t) = log(n)^O(t) * log(1/epsilon) wenn s = poly(n). Wir fixieren nunmehr epsilon = 0,1. 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) < 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 - Repraaesentation 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)/n)} 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 dim(V) = sum_{i=1..(n+sqrt(n))/2} (n ueber i) <= 0,88*2^n 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].