Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2012/13 / Komplexitätstheorie / PARITY nicht in AC0 nach Razborov und Smolensky


Inhaltsbereich

PARITY nicht in AC0 nach Razborov und Smolensky

Plain Text icon sk.txt — Plain Text, 14 KB (14444 bytes)

Dateiinhalt

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 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 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_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<i<=l so waehlen, dass t:=|S_(i-1) & T| > 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 

(Bedingte Wahrscheinlichtkeit: Pr("=1" | "<=1") = Pr("=1") / Pr("<=1")). 


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).) Der Grad des entstehenden Polynoms ergibt sich 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 = 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) 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]. 

Artikelaktionen


Funktionsleiste