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 x<n so gilt x^(n-1) = 1 (mod n). 
Beweis: Phi(n) = n-1 und x:Phi(n) in diesem Falle. 

Lemma: Falls x nicht in Phi(n), so ist x^(n-1) verschieden von 1 mod
n.
Beweis: Sei b=ggT(n,x)>1 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 mit x^(n-1) verschieden von 1 mindestens 50%. 

Beweis: Sei K_n = {x | x^(n-1)=1 (mod n)}. K_n bildet eine Untergruppe
von Phi(n). Somit gilt |K_n| | phi(n). Falls jetzt K_n nicht gleich
Phi(n) ist, so ist |K_n| <= phi(n) / 2. Die Zahl derjenigen x fuer die
gilt x^(n-1) # 1 ist groesser oder gleich  n-1-phi(n) + phi(n)/2 >=
(n-1)/2. 

Wenn wir von einer Zahl wissen, dass sie keine Carmichael Zahl ist,
dann koennen wir zufaellig eine Zahl x<n waehlen und x^(n-1) mod n
bestimmen. Ist dieser Wert von 1 verschieden, so wissen wir, dass n
zusammengesetzt ist. Ist auf der anderen Seite n zusammengesetzt, so
wird dieses Ereignis mit Wahrscheinlichkeit >=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<n sodass ein i
existiert mit ggT(x^[(n-1) / 2^i] - 1, n) > 1 ist >= 75%. 

Beweis: Siehe Bovet-Crescenzi. 

Miller-Rabin Algorithmus: Eingabe n. Wiederhole die folgende Prozedur a Mal. 
Waehle zufaellig x<n. 
Bestimme u := x^(n-1) mod n. Falls u > 1, so antworte "n ist
zusammengesetzt". Falls u = 1, so pruefe, ob i<log n existiert mit
ggT(x^[(n-1)/2^i] - 1,n) > 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<=i<j <=n ein. Der Graph
G hat ein perfektes Matching genau dann, wenn die Determinante der
Matrix A = (a_ij) nicht verschwindet, wobei 

a_ij =  x_ij falls i<j und (i,j):E
a_ij = -x_ji falls i>j 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.