Probabilistische Algorithmen und Komplexitaetsklassen. 1. Zwei Beispiele fuer probabilistische Algorithmen. Der Miller-Rabin Primzahltest. ============================== Gegeben eine natuerliche Zahl n. Man entscheide, ob n eine Primzahl ist. Komplexitaetsmass: Laenge der Eingabe = O(log n). Primfaktorzerlegung etc liefert daher Algorithmen mit exponentieller Laufzeit. Lemma: Sei G eine kommutative (=abelsche) Gruppe, und U eine Untergruppe. |U| ist ein Teiler von |G|. Beweis: Wir notieren das Inverse von x mit x'. Betrachte Aequivalenzrelation x~y <=> xy' in U. Alle Aequivalenzklassen sind gleich gross: x:[a] <=> xa'b:[b]. Naemlich xa'bb'=xa'. Aber U=[1]. Lemma: Sei x:G, dann x^|G|=1. Beweis: Betrachte 1,x,x^2,x^3,x^4,.... (Rho Diagramm). Diese Elemente bilden eine Untergruppe U. Klarerweise gilt x^|U|=1: Falls schon frueher 1 kaeme, so wuerden sich ja die Elemente wiederholen, falls spaeter die 1 kommt, so waere die Untergruppe groesser. Nach vorigem Lemma gilt |U| | |G|, also x^|G|=1. Definition: Sei n natuerliche Zahl und Phi(n) die Menge der zu n teilerfremden Zahlen < n. Z.B.: Phi(15) = {1,2,4,7,8,11,13,14}. Phi(n) bildet mit Multiplikation modulo n eine Gruppe. Inverses: a:Phi(n). Bestimme mit Euklid u,v sodass un+va=1. Dann ist v ein Inverses zu n mod a. Es folgt ausserdem v:Phi(n). Sei phi(n)=|Phi(n)|. Lemma: Fuer x:Phi(n) gilt x^phi(n) = 1 (mod n) Lemma (Fermat): Ist n Primzahl und x1 und a := x^(n-1) mod n und v := x^(n-2) mod n. Es ex u sodass xv + un = a, damit ist aber b ein Teiler von a. Definition: n ist Carmichael Zahl, wenn x^(n-1) = 1 (mod n) fuer alle x:Phi(n). Satz: Sei n keine Carmichael Zahl. Falls n nicht prim ist, so ist der Anteil derjenigen x= (n-1)/2. Wenn wir von einer Zahl wissen, dass sie keine Carmichael Zahl ist, dann koennen wir zufaellig eine Zahl x=50% eintreten. Wir wiederholen wir diese Prozedur k Male mit unabhaengigen Zufallszahlen. Kommt auch nur ein einziges Mal #1 heraus, so wissen wir, dass die Zahl zusammengesetzt war. Kommt dagegen immer 1 heraus, so muss zwar n nicht prim sein, aber die Wahrscheinlichkeit, dass n trotzdem zusammengesetzt ist, ist <= 2^(-k). Waehlen wir z.B. k=100, so ist diese Wahrscheinlichkeit deutlich kleiner als der eines Rechenfehlers durch kosmische Strahlung. Leider gilt das nicht fuer Carmichael Zahlen, da ja hier nur fuer die x-Werte aus dem Komplement von Phi(n) ein Wert #1 herauskommt. Und deren Anteil wird mit wachsendem n immer kleiner. Dummerweise gibt es unendlich viele Carmichael Zahlen, die ersten 3 Beispiele sind 3.11.17, 5.13.17, 7.13.19. Auf der anderen Seite ist aber die Eigenschaft, x^(n-1)=1 fuer alle x:Phi(n), die ja bei Carmichael Zahlen der Fall ist, so "stark", dass man daraus eine weitere Bedingung ableiten kann, welche dann auf den Miller-Rabin Test fuehrt: Satz: Sei n Carmichael Zahl. Der Anteil derjenigen x 1 ist >= 75%. Beweis: Siehe Bovet-Crescenzi. Miller-Rabin Algorithmus: Eingabe n. Wiederhole die folgende Prozedur a Mal. Waehle zufaellig x 1, so antworte "n ist zusammengesetzt". Falls u = 1, so pruefe, ob i 1. Falls ja, so antworte "n ist zusammengesetzt". Wurde nach a Malen nicht geantwortet, so antworte "n ist prim". Satz: Sei n eine beliebige Zahl. Antwortet der Miller-Rabin Algorithmus "n ist zusammengesetzt", so ist n tatsaechlich zusammengesetzt. Ist n prim, so antwortet der Miller-Rabin Algorithmus "n ist prim". Ist n zusammengesetzt, so ist die Wahrscheinlichkeit dafuer, dass der Miller-Rabin Algorithmus (faelschlicherweise) antwortet "n ist prim" <= 2^-a. Verschwinden von Polynomen. =========================== Wir betrachten folgendes Problem. Gegeben sei ein Polynom p vom Grad <=d in n Variablen. Man entscheide, ob p=0. (Konstanten haben Grad 0, Variablen haben Grad 1. Hat p Grad <= d1 und q Grad <= d2, so hat p1+p2 Grad <= max(d1,d2) und p1.p2 hat Grad <= d1+d2. Ein Polynom p hat Grad d, wenn es Grad <= d aber nicht Grad <= d-1 hat.) Durch Ausmultiplizieren laesst sich diese Frage entscheiden. Beispiel: (a^2+b^2+c^2+d^2)(A^2+B^2+C^2+D^2) - (aA+bB+cC+dD)^2 - (aB-bA-cD+dC)^2 - (aC+bD-cA-dB)^2 - (aD-bC+cB-dA)^2 = 0 (Das Polynom hier hat Grad 4). Allerdings ist die Zahl der Monome Theta(d^n) und es koennen entsprechend lange Zwischenergebnisse entstehen, selbst wenn das urpsruenglich gegebene Polynom recht kurz ist. Man bedenke, dass sich beim Multiplizieren die Zahl der Monome i.a. quadriert ("jedes mit jedem"). Ein Entscheidungsverfahren mit polynomialer Laufzeit ist nicht bekannt, wohl aber laesst sich mithilfe von Zufall aehnlich wie beim Primzahltest sehr schnell mit an Sicherheit grenzender Wahrscheinlichkeit feststellen, ob ein Polynom verschwindet. Die Idee ist es, fuer die Variablen zufaellige Werte einzusetzen und zu schauen, ob immer Null herauskommt. Lemma: Sei p ein nichtverschwindendes Polynom in n Variablen x1..xn und vom Grad <=d. Sei N>0 beliebig. Die Zahl derjenigen xs : {-N..N}^n, sodass p(xs)=0 ist <= dn(2N+1)^(n-1). Beweis durch Induktion ueber n. Ist n = 1, so gibt es ueberhaupt hoechstens d Nullstellen. Anderenfalls schreiben wir p in der Form p(x,ys) = p_k(ys).x^k + p_(k-1)(ys).x^(k-1) + ... + p_1(ys).x + p_0 wobei p_k # 0 und k<=d. Die p_i sind hier Polynome vom Grad <= d in n-1 Variablen. Waeren alle p_i = 0, so auch p selbst, was wir ja ausgeschlossen hatten. Wie muessen nun x und ys beschaffen sein, damit p=0 wird? Zu jedem ys gibt es maximal d viele x. Ausserdem koennte noch sein, dass p_k(ys) Null wird, in welchem Falle dann (moeglicherweise) x beliebig gewaehlt werden kann. Das macht also insgesamt d(2N+1)^(n-1) + d(n-1)(2N+1)^(n-2)(2N+1) = dn(2N+1)^(n-1). Waehlt man also N=nd, so ist der Anteil derjenigen xs fuer die 0 herauskommt hoechstens dn(2dn+1)^(n-1) / (2dn+1)^n <= dn/(2dn+1) <= 50%. Wobei wir natuerlich recht grosszuegig abgeschaetzt haben. Daraus resultiert folgender randomisierter Algorithmus: Eingabe p vom Grad <= d und n Variablen. Wiederhole die folgende Prozedur t Mal. Waehle zufaellig xs : {-nd..nd}^n. Bestimme u := p(xs). Falls u # 0, so antworte "p # 0". Wurde nach a Malen nicht geantwortet, so antworte "p = 0". Satz: Ist p=0 so lautet die Antwort mit Sicherheit "p = 0". Ist dagegen p != 0, so ist die Wahrscheinlichkeit einer Antwort "p = 0" kleiner gleich 2^-t. Anwendung: Perfektes Matching ============================= Gegeben ein ungerichteter Graph (V,E). Ein perfektes Matching ist gegeben durch eine Auswahl E' der Kanten, sodass keine zwei Kanten in E' einen Knoten gemeinsam haben, aber jeder Knoten von einer Kante in E' beruehrt wird. ("Perfekt" bezieht sich auf die zweite Bedingung. Ist nur die erste erfuellt, so liegt ein Matching vor.) Oft haben die Kanten noch Gewichte und man fragt nach einem perfekten Matching minimalen Gewichts. Natuerlich kann es ein perfektes Matching nur bei gerader Knotenzahl geben. Man entscheide, ob ein perfektes Matching existiert. Dafuer gibt es einen deterministischen PTIME Algorithmus, aber der ist recht kompliziert. Blumen und Wassergraeben spielen eine Rolle. Hier wollen wir sehen, wie der vorgenannte Algorithmus gestattet, mit an Sicherheit grenzender Wahrscheinlichkeit korrekt festzustellen, ob ein perfektes Matching existiert. Durch wiederholtes Aufrufen kann man damit auch ein Matching berechnen, falls eines existiert. Satz (Tutte): Sei G=(V,E) ungerichteter Graph mit Knotenmenge V={1,...,n}. Wir fuehren Variablen x_ij fuer 1<=ij und (i,j):E Die Matrix (a_ij) ist also schiefsymmetrisch (A transponiert = -A). Auf der Hauptdiagonalen stehen Nullen. Die Determinante ist aber ein Polynom vom Grad n und kann fuer feste Werte in Zeit O(n^3) ausgewertet werden (mit Gaussverfahren). Beweis des Satzes von Tutte: Fuer pi eine Permutation auf {1..n} bezeichne P(pi) das Produkt ueber a_(i,pi(i)) fuer i=1..n. Die Determinante der Matrix ist definitionsgemaess gleich der Summe der P(pi)*sign(pi) erstreckt ueber alle Permutationen pi. Hierbei bezeichnet sign(pi) das "Signum der Permutation pi". Dies ergibt sich als Produkt der (-1)^l_i wobei l_i die Laengen der Zyklen von pi durchlaeuft. Insbesondere ist sign(pi)=1, falls pi eine Permutation ist, welche nur aus Zweierzyklen besteht, also pi2=1 und pi(x) != x fuer alle x. Der Ausdruck P(pi) ist nur dann von Null verschieden, wenn (i,pi(i)):E fuer alle i. Ausserdem heben sich in der Summe alle Beitraege von Permutationen mit ungeraden Zyklen gegeneinander auf. Betrachten wir alle Permutationen eines bestimmten Typs, der einen ungeraden Zyklus enthaelt. Hat man eine Permutation pi dieses Typs, so erhaelt man eine andere Permutation pi' desselben Typs, indem man in diesem ungeraden Zyklus die Richtung umdreht. Es gilt aber P(pi') = - P(pi') wegen der Schiefsymmetrie. Deshalb heben sich die Beitraege dieser Permutationen allesamt auf. Es bleiben die Beitraege derjenigen Permutationen, deren saemtliche Zyklen gerade Laenge haben. Diese koennen sich nicht gegenseitig aufheben, da zwei Permutationen mit ausschliesslich geraden Zyklen entweder denselben Beitrag liefern (das passiert genau dann, wenn sie sich nur durch Umorientierung einer oder mehrerer Zyklen voneinander unterscheiden), oder aber unterschiedliche Kanten benutzen und damit ein unterschiedliches Variablenprodukt betreffen. Zusammengefasst ist also die Determinante genau dann von Null verschieden, wenn es mindestens eine Permutation gibt, die nur gerade Zyklen hat. Das aber ist genau dann der Fall, wenn ein perfektes Matching existiert: jedes perfekte Matching liefert offensichtlich eine Permutation, die nur aus Transpositionen besteht. Aus jeder Permutation mit ausschl. geraden Zyklen kann man ein Matching ablesen, indem man von jedem Zyklus genau jede zweite Kante auswaehlt. Im Buch [Bovet] steht noch eine genauere Analyse der Determinante, die deren exakte Form und nicht nur deren Verschwinden mit den Matchings in Beziehung setzt. M.E. enthaelt die aber technische Fehler. 2. Probabilistische Komplexitaetsklassen. Definition: Die Komplexitaetsklasse PP umfasst alle Probleme A fuer die es eine nichtdeterministische Maschine gibt mit den folgenden Eigenschaften. i) Die Laufzeit ist immer die gleiche, unabhaengig von den nichtdeterministischen Auswahlen und ist ausserdem polynomial in der Eingabelaenge. ii) Zu jedem Zeitpunkt stehen genau 2 nichtdeterministische Folgezustaende zur Wahl. (Ggf kuenstlich). iii) Es ist x:A, genau dann, wenn der Anteil der akzeptierenden Berechnungen (deren Anzahl ist <= d^p(|x|)) >= 50%. Eine Maschine mit den ersten beiden Eigenschaften heisst probabilistische Turingmaschine. Liegt eine PP Maschine vor, so kann man die nichtdeterministischen Entscheidungen zufaellig treffen, sodass also alle moeglichen Berechnungen gleichwahrscheinlich sind. Man kann dann akzeptieren, falls die Maschine akzeptiert. In diesem Falle ist die Wahrscheinlichkeit, einen Fehler zu machen zwar < 50%, kann aber sehr nahe an 50% herankommen. Eigentlich ist die Klasse PP eher von theoretischer Bedeutung. Zur praktischen Berechnung ist ein PP-Algorithmus nicht brauchbar. Satz: NP in PP Beweis: Gegeben eine NP-Maschine M fuer L. Zu Beginn mit 50% entscheiden, ob einfach so akzeptiert wird, oder weitergemacht wird. In letzterem Falle M simulieren und nichtdet. als Zufall interpretieren. Satz: PP in PSPACE Satz (Toda): Falls PP=PSPACE, so kollabiert die polynomiale Hierarchie. Definition: Ein Problem A liegt in der Klasse BPP, falls es eine probabilistische Maschine gibt derart dass: Falls x:A, so ist der Anteil der akzeptierenden Berechnungen >=75% Falls x nicht in A, so ist der Anteil der akzeptierenden Berechnungen <=25%. Satz: Sei A in BPP und q ein Polynom. Es existiert eine probabilistische TM sodass x:A => Prob(Akzeptanz) >= 1-exp(-p(|x|)) und x nicht in A => Prob(Akzeptanz) <= exp(-p(|x|)). Beweis: Die Fehlerwahrscheinlichkeit kann (durch Wahl eines konstanten Polynoms, z.B. q=100) beliebig klein gemacht werden und sogar so, dass sie mit wachsender Eingabegroesse immer kleiner wird. Man laesst eine BPP Maschine fuer A t = t(|x|) Mal laufen und akzeptiert, falls in der Mehrzahl der Male akzeptiert wurde. Sei x:A. Die Anzahl der akzeptierenden Male ist binomialverteilt mit Parameter p=0,75. Chernoff-Schranke (s.u.): Die Wahrscheinlichkeit, dass diese Anzahl <= (1-delta)pt ist, ist <= exp(-delta^2/2 pt). Wir lehnen ab, falls die Anzahl der akzeptierenden Durchfuehrungen kleiner als t/2 ist, also brauchen wir (1-delta)*0,75*t = 0,5*t, also (1-delta) = 2/3, also delta=1/3. Diese W soll kleiner als exp(-q(|x|)) werden, also muss gelten: exp(-delta^2/2 pt) <= exp(-q(|x|)), also q(|x|) <= delta^2/2 p t, also t >= 24 q. Falls umgekehrt x nicht in A liegt, so ist die Zahl der (dennoch) akzeptierenden Berechnungen binomialverteilt mit Parameter p=0,25. Die Wahrscheinlichkeit dafuer, dass diese Zahl >= (1+delta)pt ist, ist <= [exp(delta)/((1+delta)^(1+delta))]^pt. Im Beispiel ist pt=t/4 und (1+delta)pt soll t/2 werden, also delta=1. Nun ist e/4 = exp(-0,386), also brauchen wir 0,386*0,25*t >= q(|x|), also t >= 11 q. Mit t >= 24q sind wir also auf der sicheren Seite. Hier noch einmal die Chernoff Ungleichung in allgemeiner Form. Satz (Chernoff-Schranken): Seien X_1..X_t 0-1-Zufallsvariablen mit Pr(X_i=1) = p_i. Sei S=X_1+...+X_t. Es gilt mu=E[S]=p_1+...+p_t. Sei delta>0. Pr(S >= (1+delta)mu) <= [exp(delta)/((1+delta)^(1+delta))]^mu Pr(S<=(1-delta)mu) <= exp(-delta^2/2 mu). Definition: Ein Problem A liegt in der Klasse RP, auch R, falls es eine PTM gibt, sodass gilt x:A <= Prob(akzeptiert)=0.5 und x nicht in A => Prob(akzeptiert)=0. Definition: Die Klasse ZPP ist definiert als RP geschnitten mit co-RP. Bemerkung: Ein Problem A liegt genau dann in der Klasse ZPP, wenn es eine PTM gibt mit zusaetzlichem Zustand "unentschieden", derart dass gilt: M akzeptiert x => x:A, M lehnt x ab => x nicht in A, Prob(Berechnung von M auf x endet in "unentschieden") <= 0,5. Bemerkung: Ein Problem A liegt genau dann in der Klasse ZPP, wenn es eine Turingmaschine gibt, die Zufallsentscheidungen trifft aber immer korrekt antwortet und deren erwartete Laufzeit polynomial ist. In der einen Richtung laesst man die ZPP Maschine immer wieder laufen, bis irgendwann mal entschieden wird. Wenn man will, kann man parallel dazu noch mit exponentiellem Aufwand den ganzen Baum durchgehen, damit man auf jeden Fall irgendwann mal terminiert. In der anderen Richtung laesst man eine feste Zeit laufen und schaltet dann ab. Wurde kein Ergebnis erzielt, so lautet die Antwort "unentschieden". Die erforderliche Zeitschranke kann polynomial in der Eingabelaenge gewaehlt werden. Weitere Terminologie: Monte-Carlo-Algorithmus: Algorithmus, der Wahrscheinlichkeit benutzt und moeglicherweise falsche Antworten liefert, wenn auch mit kleiner Wahrscheinlichkeit. (Bsp: Algorithmen in PP,BPP,RP,co-RP) Las Vegas Algorithmus: Liefert nur richtige Antworten, kann aber mit gewisser Wahrscheinlichkeit keine Antwort liefern (Bsp: Algorithmen in ZPP, randomisiertes Quicksort) Theorem: P <= ZPP, RP u co-RP <= BPP R <= NP, co-RP <= co-NP BPP <= PP NP u co-NP <= PP <= PSPACE PP, BPP, ZPP abgeschlossen unter ~, BPP, RP, ZPP abgeschlossen unter u und &. Beweis: leicht. Theorem (Beigel et al) PP ist abgeschlossen unter Durchschnitt. Beweis (schwierig) Satz: Falls SAT in BPP, so auch SAT in RP. Beweis: Aufgrund der Selbstreduzierbarkeit von SAT. Waehle eine Variable x. Teste mit dem BPP Algorithmus, ob phi(x=0) und/oder phi(x=1) erf'bar ist. Setze x entsprechend und fahre mit der reduzierten Formel fort. Auf diese Weise entsteht durch insgesamt 2n (wobei n = Zahl der Variablen) Aufrufe des BPP Algorithmus eine Bewertung, die mit hoher W die Formel erfuellt. Zum Schluss pruefen wir ab, ob diese Bewertung tatsaechlich die Formel erfuellt. Ist phi unerfuellbar, so wird mit Sicherheit abgelehnt. Ansonsten wird mit hoher W akzeptiert. Erinnerung: P/poly ist die Klasse derjenigen Probleme, fuer die es ein Polynom q gibt, sodass fuer alle n ein Schaltkreis C_n der Groesse q(n) existiert, derart dass C_n alle Instanzen der Groesse n korrekt entscheidet. Satz: BPP <= P/poly. Die Beweisidee ist, dass aufgrund der Wahrscheinlichkeitsverstaerkung fuer jede Eingabe ein so enorm grosser Anteil der moeglichen Zufallsentscheidungen zum richtigen Ergebnis fuehrt, dass es mindestens eine Art der Zufallsentscheidungen geben muss, die fuer alle Eingaben einer bestimmten Groesse zum Erfolg fuehrt. Diese Folge der Zufallsentscheidungen kann man dann im Schaltkreis C_n fest verdrahten. Sei also A in BPP und M eine BPP-PTM mit Laufzeit p(n). Es gibt oBdA 2^n Eingaben der Laenge n. Wir richten es so ein, dass die Fehlerwahrscheinlichkeit kleiner als 1/2^(n+1) ist. Somit ist fuer jede Eingabe der Laenge x ein Anteil von <= 1/2^(n+1) der Zufallsentscheidungen unguenstig. Der Anteil derjenigen Zufallsentscheidungen, die fuer mindestens eine der Eingaben unguenstig ist, ist also <= 2^n * 1/2^(n+1) = 1/2. Daher sind mindestens 50% der Wahlen der Zufallsentscheidungen fuer alle Eingaben guenstig und eine dieser Wahlen kann fest verdrahtet werden.