Untere Schranke fuer die Paritaetsfunktion (nach U Schoening, Perlen der Th.Inf.) 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. Im Gegensatz dazu 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. Der Rest dieser Notiz bildet den Beweis des folgenden Satzes: Satz: PARITY ist nicht in AC0. Die Bedeutung dieses Ergebnis 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. Lemma: Mit Tiefe 1 laesst sich PARITY nicht berechnen. Beweis: Die Paritaetsfunktion fuer z.B. n=2 waere dann ein UND oder ein ODER von zwei Literalen. Das ist aber nicht so. Lemma: Mit Tiefe 2 laesst sich PARITY nicht mit polynomiell vielen Gattern berechnen (wohl aber mit exponentiell vielen wg DNF) Beweis: Nehmen wir an es ginge doch und der Schaltkreis S_n sei ein ODER von UNDs. Jedes UND auf der ersten Stufe muss von allen n Variablen abhaengen. Hinge es naemlich von x nicht ab, so betrachten wir die Belegung der uebrigen Variablen, die das UND wahrmachen. Mit der wird dann auch das ODER wahr und somit kommt 1 raus unabhaengig von x. Das stimmt aber nicht fuer die Paritaetsfunktion. Somit muss fuer jede der Bewertungen eta, fuer die par_n(eta) 1, ist ein eigenes UND vorhanden sein, das sind aber 2^{n-1} viele. Der Fall, dass der Schaltkreis ein ODER von UNDs ist geht analog, wobei man 1 und 0 vertauscht. Wir machen uns nun die folgende wichtige Beobachtung zunutze: Beobachtung: Berechnet S_n die Paritaetsfunktion und ist eta eine Bewertung von n'2)) d) Aus diesen Annahmen werden wir nunmehr einen Widerspruch herleiten. Und zwar konstruieren wir aus der Schaltkreisfamilie S_n eine neue Schaltkreisfamilie S'_n mit konstantem Eingangsfanin, die auch PARITY berechnet, aber eine Tiefe =k haben und auch das Eingangsfanin von S'_n wird groesser als c, aber immer noch konstant sein. Um S'_n zu bauen, beginnt man mit S_(4n^2). Man zeigt dann, dass es eine Auswahl von 4n^2-n der Eingangsvariablen von S_(4n^2) gibt und eine Belegung auf diesen, sodass der resultierende Schaltkreis durch Anwendung des Distributivgesetzes auf der untersten Schicht tiefenmaessig um eins reduziert werden kann. Den Schaltkreis S'_n erhaelt man dann durch de Morgan Dualisierung falls noetig (also falls die gewaehlte Belegung eine ungerade Zahl von Variablen mit 1 besetzt hat). Die Existenz dieser Auswahl und Belegung beweist man mit der probabilistischen Methode. Dafuer ist es guenstiger, statt 4n^2 n zu schreiben, d.h. man beweist: Fuer jedes hinreichend grosse n existiert eine partielle Belegung der n Variablen, die mindestens sqrt(n)/2 Variablen uebriglaesst, und so dass der resultierende Schaltkreis durch Anwendung des Distributivgesetzes auf Tiefe t-1 reduziert werden kann und dennoch polynomielle Groesse und konstanten Eingangsfanin aufweist. Hierzu verwenden wir folgende Zufallssubstitution: x_i bleibt mit W. 1/sqrt(n) bestehen, x_i=0 mit W. (1-1/sqrt(n))/2 x_i=1 mit W. (1-1/sqrt(n))/2 Das Bestehenbleiben von Variablen ist ein Bernoulli Experiment mit p=1/sqrt(n) und Varianz npq. Lemma: Pr("weniger als sqrt(n)/2 Variablen bleiben") = O(1/sqrt(n)). Beweis: Mit Tschebyscheff Ungleichung: Pr(|X-E(X)|>=a) <= V(X)/a^2. Also Pr(...) <= Pr(|X-sqrt(n)|>=sqrt(n)/2) <= sqrt(n)/4n = O(1/sqrt(n)). Bemerkung: Alle O-Notationen beziehen sich auf von n unabhaengige Konstanten. So bedeutet W. <= O(1/sqrt(n)), dass z.B. gilt W<=100/sqrt(n) fuer n>=10000, oder auch W<=10k^2*2^c/sqrt(n) fuer n>=c^c^k. Fuer das weitere benoetigen wir folgenden Hilfssatz, dessen Beweis wir zunaechst veschieben. Satz: Fuer jedes c:N und k:N existiert e:N sodass folgendes gilt: Sei ein Schaltkreis f der Tiefe 2 ueber n Variablen gegeben, bestehend aus einem UND Gatter, unterhalb dem sich O(n^{k-1}) viele ODER Gatter mit fanin <= c befinden. Die Eingaben werden der o.a. Zufallssubstitution unterworfen. Die W. dafuer, dass im resultierenden Schaltkreis (nach Vereinfachung) das UND Gatter von mehr als e vielen Variablen abhaengt, ist O(1/n^k). [] Wir setzen diesen Satz zunaechst voraus und beweisen damit die Existenz der wuenschenswerten Substitution. Also: Sei e die Zahl aus dem obigen Satz. Fuer jedes der O(n^(k-1)) UND-Gatter ist die W. dass es von mehr als e Variablen abhaengt O(1/n^k). Die W. dafuer dass nach der Zufallssubstitution weniger als sqrt(n)/2 Variablen uebrigbleiben oder aber auch nur eines der UND Gatter von mehr als e Variablen abhaengt, ist O(1/sqrt(n) + n^(k-1)/n^k) = O(1/n+1/sqrt(n)). Somit existiert fuer hinreichend grosses n eine Substitution von n-sqrt(n)/2 Variablen, die als sqrt(n)/2 ueberiglaesst und gleichzeitig dazu fuehrt, dass *alle* UND Gatter nur von hoechstens e vielen Variablen abhaengen. Jedes der UND Gatter mit seinen darunterliegenden ODER Gattern kann dann aber als DNF konstanter Groesse geschrieben werden (ein ODER von 2^e UNDs von fanin jeweils e). Das nunmehr oben stehende ODER kann dann aber mit dem ODER der naechsten Schicht verschmolzen werden, wodurch ein Schaltkreis der Tiefe hoechstens t-1 entsteht. Es verbleibt der Beweis des obigen Satzes. Dieser erfolgt durch Induktion ueberdas Eingangsfanin c. Induktionsanfang c=1. Wir haben es also de facto mit einem UND von Literalen zu tun. Wir unterscheiden zwei Faelle: Fall a) fanin des UND Gatters >= 4k*ln(n). Hier wird das UND Gatter mit hoher W zu Null, haengt also von 0 Variablen ab. Lemma: Pr(UND Gatter wird nicht zu Null)=O(1/n^k) Beweis: Damit das UND Gatter nicht Null wird, darf kein Eingang zu Null werden. Die W dass ein Eingang nicht Null wird ist <=3/4 (falls n>=4). Die gesuchte W. ist also <= (3/4)^(4k ln(n)) = n^(4k ln(1-1/4)) <= n^(-k). Im Fall a) setzen wir also e:=0. Fall b) fanin des UND Gatters < 4k*ln(n). Hier ist es unwahrscheinlich, dass von den Variablen, von denen das Gatter abhaengt, viele uebrigbleiben. Lemma: Pr(UND Gatter haengt von mehr als 18k Eingaben ab) = O(1/n^k) Beweis mithilfe der Abschaetzung Pr(X>=a)<=p^a*2^n wenn X (n,p)-bernoulliverteilt. Wir koennen also in diesem Fall e:=18k setzen. Nunmehr kommen wir zum Induktionsschritt, in welchem c>1 ist. Es sei e' der fanin aus der Induktionsvoraussetzung fuer c-1 und k. Wieder unterscheiden wir zwei Faelle, wobei jeweils d:=k*4^c. Fall c) das UND Gatter hat (vor der Zufallseinsetzung) mindestens d*ln(n) variablendisjunkte ODER Gatter unter sich. Hier ist es wahrscheinlich, dass eines dieser ODER Gatter, die ja fanin c haben, zu Null wird (alle Inputs Null) und dadurch das UND Gatter "killt". Lemma: Pr(UND Gatter wird nicht konstant 0)=O(1/n^k). Beweis: Da die ODER Gatter variablendisjunkt sind, ist ihr Verhalten paarweise unabhaengig. Die W. dass eines von ihnen nicht Null wird, ist <= (1-4^(-c)). Dieses muss sich d*ln(n) Mal unabhaengig voneinander ereignen. Die Ges.W. ist daher <= (1-4^(-c))^(d*ln(n))= n^(d*ln(1-4^(-c))) <= n^(-d*4^(-c))=n^(-k). Fall d) das UND Gatter hat (vor der Zufallseinsetzung) weniger als d*ln(n) (wobei d=k*4^c) variablendisjunkte ODER Gatter unter sich. Hier waehlt man eine maximale Menge variablendisjunkter ODER Gatter unterhalb des UND Gatters und bezeichnet mit H die Menge der Variablen, von denen diese ODER Gatter abhaengen. Diese Menge H hat hoechstens c*d*ln(n) Elemente und jedes der ODER Gatter unterhalb des UND Gatters enthaelt mindestens eine Variable aus H, sonst haette man es ja der maximalen Menge zuschlagen koennen. Es sei l := 2^(|H|) <= 2^(c*d*ln(n)) die Zahl der Moeglichkeiten, diese Variablen zu belegen. Setzt man eine solche Belegung ein, so faellt in jedem ODER also eine Variable weg, es hat somit fanin c-1 (oder 0). Daher kann man das UND-Gatter mit seinen darunterliegenden ODERs in eine Art DNF der Form \/_eta M_eta /\ f_eta entwickeln, wobei das grosse ODER ueber alle solche Belegungen eta rangiert (l an der Zahl) und M_eta der zu eta gehoerige Minterm ist, also eine Konjunktion ueber Literale aus H, die gerade von eta wahrgemacht wird, und schliesslich f_eta die Restformel nach Einsetzen von eta ist, in der also alle ODERs ein fanin <= c-1 haben. Wenn etwa H={x,y} und unser Schaltkreis wie folgt aussieht f := (x|~y|z) & (~x|z|w) & (~y|z|t) & (x|y|t) & (x|~w|~t) so koennen wir f umschreiben zu ~x&~y&f_00 | ~x&y&f_01 | x&~y&f_10 | x&y&f_11 wobei f_00=f[x:=0,y:=0] = t & (~w|~t) f_01 = z & (z|t) & (~w|~t) f_10 = z|w f_11 = (z|w) & (z|t) Es sei nun h die Zahl der Variablen aus H, die nach der Zufallssubsitution noch uebrigbleibt. Mit hoher W. ist diese konstant: Lemma: Pr(h > 4cd+2k) = O(1/n^k) Beweis: |H|<=c*d*ln(n). Also Pr <= 2^(c*d*ln(n)) * (1/sqrt(n))^(4cd + 2k) Mit hoher W besteht daher die obige DNF-artige Darstellung nur aus m := 2^(4cd+2k) Termen. Wir setzen dann e:=2^(4cd+2k)*e' + 4cd+2k und rechnen: Pr(f haengt von mehr als e Variablen ab) <= Pr(h>4cd+2k) + m*Pr(ein festes f_eta haengt von mehr als e' Variablen ab) <= O(1/n^k) + m*O(1/n^k) = O(1/n^k). Q.E.D.