14.10. Vorstellung der zu behandelnden Themen. Turingmaschinen Basics. Evidenz fuer und gegen P=NP. Zeitkomplexitaet ueber NP (EXPTIME, PH). Platzkomplexitaet; hier speziell Ergebnisse von programmiersprachlicher Relevanz, z.B. Satz von Savitch, Satz von Cook. LOGSPACE und P-Vollstaendigkeit. Komplexitaet probabilistischer Berechnung; insbes. IP=PSPACE als Beispiel eines gelungenen Beweises einer lange offenen Vermutung. Optional Parallele Komplexitaetsklassen ODER Komplexitaet und Programmiersprachen. k-Band Turingmaschinen. Definition, Beispiel Palindrome. Erkannte Sprache einer TM. Vernuenftige Codierung von Problemen. 21.10. Definition der Zeitkomplexitaet TIME_M(x) = Zahl der Rechenschritte, die M auf Input x durchfuehrt. Definition von Transducern, Orakelmaschinen (siehe Buch). Definition von DTIME(f) als {L | es ex. M sodass L=L(M) und TIME_M(x) <= f(|x|) fuer alle x}. NB: Im Buch beinhaltet die Definition noch eine O-Notation. Definition der zeitkonstruierbaren Funktion: f zeitkonstruierbar wenn transducer M existiert, sodass M fuer Input x ein Resultat y mit |y| = f(|x|) berechnet. Z.B. 1^(f(|x|)). Zusaetzlich TIME_M(x) <= c.|y|+d fuer feste Konstanten c, d. Alle Polynom- und Exponentialfunktionen sind zeitkonstruierbar. Die z.k. Funktionen sind unter Komposition abgeschlossen. Jede berechenbare Fkt wird durch eine z.k. majorisiert. NB: Die Definition von z.k. im Buch ist anders. Speedup-Theorem (Beschleunigungssatz): Fuer alle epsilon>0 existiert c>0 sodass DTIME(f(n)) enthalten in DTIME(max(cn,epsilon.f(n))). Beweis: In der Uebung. k-Baender in eins: Sei M eine k-Band Maschine. Es existiert eine 1-Band Maschine M' sodass L(M)=L(M') und TIME_(M')(x) = O((TIME_M(x))^2). Beweis: In der Uebung. Satz von Hennie-Stearns: Sei M eine k-Band Maschine. Es existiert eine 2-Band Maschine M' sodass L(M)=L(M') und TIME_(M')(x) = O((TIME_M(x).log(TIME_M(x))). Beweis: [Hennie and R. Stearns. Two tape simulation of multitape Turing machines. J. Assoc. Comput. Mach., 13(4):533-546, 1966] oder [N. Pippenger and M. Fischer. Relations among complexity measures. J. ACM 26, 1979] evtl auch [www.dcs.ed.ac.uk/teaching/cs4/www/cc/pipp-fisch.ps]. Zeithierarchiesatz: Sei T2 zeitkonstruierbar, T2(n) = omega(T1(n).log(T1(n))). Dann ist DTIME(T1) echt enthalten in DTIME(T2), d.h. es ex L in DTIME(T2) aber L nicht in DTIME(L1). Erklaerung: die omega-Notation besagt, dass fuer alle c>0 existiert n0>0 sodass fuer alle n>n0 gilt T2(n) >= c.T1(n). Z.B.: n^2 = omega(n.log(n)). Beweis: Wir fixieren eine vernuenftige Codierung von Turingmaschinen (mit beliebiger Bandzahl und Arbeitsalphabet). Das Eingabealphabet fixieren wir zu {0,1}. Wir bauen jetzt eine T2-zeitbeschraenkte 4-Band Maschine. Ein Band dient der Aufnahme der Beschreibung einer Maschine, zwei Baender dienen der Simulation derselben; das vierte Band verwenden wir fuer die Laufzeitbeschraenkung. Das Simulieren einer DTIME(T1) Maschine erfordert nach Hennie-Stearns c.T1(n).log(n)+d Schritte fuer geeignete Konstanten c, d. Waehlen wir n gross genug, so gilt nach Annahme T2(n) >= c.T1(n).log(T1(n))+d. Es gilt sogar epsilon T2(n) >= c.T1(n).log(T1(n))+d (***) fuer alle epsilon > 0 und genuegend grosses n. (Dividieren durch epsilon) Lassen wir die Simulation daher fuer T2(n) Schritte laufen und brechen dann ab, so erhalten wir fuer genuegend grosse Inputs das richtige Ergebnis. Konkret machen wir also folgendes: Gegeben ein Input w: 1) Schreibe auf das vierte Band epsilon.T2(|w|) viele Einser [der Wert von epsilon wird noch bestimmt.) 2) Fuehre die Simulation der durch w codierten Maschine auf Input w fuer epsilon.T2(|w|) Schritte durch (wir messen die Zahl der tatsaechlich gemachten Rechenschritte, nicht die der simulierten Schritte.) indem wir nach jedem Rechenschritt ein Symbol auf dem vierten Band wegnehmen. 3) Wurde die Simulation erfolgreich zuende gefuehrt und w akzpetiert, so weise w zurueck. 4) In allen anderen Faellen weise w zurueck. Der Wert von epsilon ist nun so zu waehlen, dass die o.a. Maschine T2(n) zeitbeschraenkt ist. Sei L die durch die o.a. Maschine M entschiedene Sprache. Angenommen, L in DTIME(T1). Es gibt daher eine Maschine M1, die L entscheidet und fuer jeden Input x nach T1(x) Schritten terminiert. Ohne Beschraenkung der Allgemeinheit koennen wir diese Maschine so waehlen, dass ihre Codierung w so gross ist, dass n:=|w| die Ungleichung (***) oben erfuellt. Somit wird M1 durch M korrekt simuliert. Wenn nun w in L, so wird w also von M akzeptiert, somit von M1 zurueckgewiesen, also w nicht in L. Ist andererseits w nicht in L, so wird w von M zurueckgewiesen, also von M1 akzeptiert, waere also in L. Ein Widerspruch. Logisch aequivalent, aber sprachlich weniger verschraenkt, kann man auch argumentieren, dass sich L von jeder Sprache L1 aus DTIME(T1) unterscheidet, da die Codierung einer genuegend grossen Maschine fuer so ein L1 in der symmetrischen Differenz von L und L1 liegt. Zur Erinnerung: Symmetrische Differenz zweier Mengen A, B ist A /\ B^c \/ B /\ B^c. *** Definition der Klasse P und FP (polynomialzeitentscheidbares und polynomialzeitberechenbares), sowie Motivation und Diskussion der Idee "P=Effizient". Siehe Buch. *** 28.10.02: Thema der naechsten zwei Stunden: Die Klasse NP. Insbesondere werden wir zeigen, das falls P=/=NP dann gibt es eine Sprache, die echt zwischen P und NP-vollstaendig liegt. Ausserdem werden wir Orakel A und B angeben, sodass P^A=NP^A und P^B=/=NP^B ist. Je nachdem, wie man also die Ausdruckskraft von Turingmaschinen durch Orakel (a.k.a. Systemaufrufe) erweitert wird die Frage P=NP einmal positiv und einmal negativ entschieden. Fuer die unrelativierte Frage ob P gleich NP ist bedeutet das natuerlich zunaechst mal gar nichts. Immerhin kann man, wenn man eine Beweisidee hat zu zeigen, dass P =/= NP erstmal pruefen, ob sich dieser "Beweis" evtl auf beliebige Orakel verallgemeinert. Falls ja, dann kann man die Beweisidee gleich wegschmeissen. Zum Beispiel geht der Diagonalisierungsbeweis des Zeithierarchiesatzes von letzter Woche ohne jede Aenderung auch in Gegenwart beliebiger Orakel durch. Ein aehnlich einfaches Diagonalisierungsargument scheidet also zur Beantwortung der Frage P=NP eher aus. Wirklich gemacht haben wir heute folgendes: Definition der Klasse NP. NP-Vollstaendigkeit. Intuitive Beweise, dass SAT NP vollstaendig ist und dass 2SAT in P ist. Ausserdem habe ich erwaehnt, dass NP in DTIME(2^polynom(n)) enthalten ist, weil man ja alle O(2^p(n)) Moeglichkeiten, die eine p(n)-zeitbeschraenkte Turingmaschine hat alle der Reihe nach "durchnudeln" kann. Statement des Satzes von Ladner-Schoening von der uniformen Diagonalisierbarkeit: Beginn des Beweises. (Alles siehe Buch, aber Vorsicht: dort steht drin, dass man fuer jedes i ein z in G finden muesse, sodass z in L_j Delta L(M^j_i). Was man aber wirklich braucht ist folgendes: Fuer jedes i ein z in G sodass z in L_1 Delta L(M^1_i) und zusaetzlich fuer jedes i ein z in G^c sodass z in L_2 Delta L(M^2_i).) 4.11.: Der letztes Mal angefangene Beweis des Satzes von der uniformen Diagonalisierung wurde zuende gefuehrt. Ausserdem wurde die folgende Anwendung angesprochen: C1 = P, C2 = NP, L1 = SAT, L2 = 0. Falls P=/=NP, so sind die Voraussetzungen des Satzes erfuellt und man erhaelt eine Sprache, die zwar in NP \ P lieget, aber nicht NP vollstaendig ist. Als naechstes wurde gezeigt, dass P^A = NP^A, wobei A die folgende Sprache ist: {(x,M,0^k) | M akzeptiert x und verbraucht dabei hoechstens k Bandfelder}. Dann wurde folgender Satz angekuendigt: Es gibt eine Menge C, sodass P^C =/= NP^C. Zu beliebiger Sprache A definierten wir L_A als {0^k | es ex. x in A mit |x|=k}. Sicher ist L_A in NP^A. Es wurde gezeigt, dass man zu jeder polynomial zeitbeschraenkten Orakelmaschine M eine Menge A finden kann, sodass L_A =/= L(M^A). Naechstes Mal zeigen wir, dass man so ein A sogar unabhaengig von M waehlen kann, womit der Satz bewiesen ist. Themen fuer die naechsten Mal(e): Levin's Suchtheorem: Man kann einen konkreten Algorithmus fuer SAT angeben, dessen Laufzeit nur um einen multiplikativen Faktor schlechter ist, als der beste den's ueberhaupt gibt (darin eingeschlossen, die die's gibt, aber noch nicht entdeckt sind.) Insbesondere laeuft dieser Algorithmus in polynomialer Zeit, wenn P=NP waere. Duenn besetzte Mengen: A ist duenn besetzt (engl. sparse), wenn |{x:A | |x|<=n}| <= p(n) fuer ein Polynom n. Satz von Mahaney: keine duenn besetzte Menge kann NP-schwierig (a.k.a. NP-hart) sein. 11.11.: Beweis des angekuendigten Satzes: es gibt eine Menge A, sodass L_A =/= L(M^A) fuer alle polynomialzeitbeschraenkten deterministischen Orakelmaschinen M, somit P^A =/= NP^A, da ja L_A in NP^A (siehe oben fuer Def von L_A). Sei M_i, i=0,1,... eine Aufzaehlung aller deterministischen polynomialzeitbeschraenkten Turingmaschinen derart dass (o.B.d.A. M_i durch p(n)=n^i+i) zeitbeschraenkt ist. Warum koennen wir das annehmen? Naja, bei jeder vernuenftigen Aufzaehlung kommt jede Maschine immer wieder dran, bzw bis dieselbe Maschine bis auf triviale Modifikationen, etwa unerreichbare Zustaende etc. Sei jetzt Maschine M etwa durch p(n)=n^5+7n^2 laufzeitbeschraenkt. Es ist p(n) <= n^i+i wenn i>=p(7).) Jetzt waehlen wir fuer jedes i ein n_i so, dass 2^n_i > Summe_{j<=i} n_i^j + j. Das geht, weil die rechte Seite selber durch ein Polynom in n_i beschraenkt ist. (Geometrische Reihe, Formel fuer die Summe der ersten i Zahlen). Wir definieren die Menge A jetzt als Vereinigung der Mengen A(i), wobei / A(i-1), falls M_i^(A(i-1))(0^n_i) akzeptiert | A(i) = < | \ A(i-1) u {x_i}, falls M_i^(A(i-1))(0^n_i) zurueckweist. Hier ist x_i ein Wort der Laenge n_i, welches in keiner der Berechnungen M_j^(A(j-1))(0^n_j) fuer j n_j<=n_i und der Bedingung an n_i. Damit die obige Setzung auch fuer i=0 Sinn macht, legen wir A(-1)=leer fest. Wir setzen jetzt A = Vereinigung aller A(i) und behaupten, dass A nicht gleich L(M_i^A) ist fuer jedes i, somit A nicht in P^A. Sei i vorgegeben. Wir betrachten die Berechnung M_i^A(0^n_i). A unterscheidet sich von A(i-1) nur um Woerter, die in M_i^(A(i-1)) (0^n_i) nicht abgefragt werden, somit gilt M_i^A(0^n_i) akzeptiert genau dann, wenn M_i^(A(i-1))(0^n_i) akzeptiert. letzteres ist aber genau dann der Fall, wenn 0^n_i nicht in L_A ist, da ja dann in der i-ten Runde eben kein Wort der Laenge n_i reingenommen wurde. QED Wir koennen daraus schliessen, dass die Frage P=?=NP nur mit solchen Methoden entschieden werden kann, die sich nicht auf beliebige Orakel verallgemeinern lassen. Die einfache Diagonalisierungsmethode, die wir etwa beim Beweis des Zeithierarchiesatzes benutzt haben, gehoert nicht dazu. Der Beweis des Zeithierarchiesatzes geht in Gegenwart beliebiger Orakel ganz genauso durch. * * * Eine Menge S heisst duenn besetzt (engl. sparse), wenn ein Polynom p existiert mit |{x in S | |x|=n}| <= p(n). Von den exponentiell vielen Woertern der Laenge n, die es insgesamt gibt, sind also nur polynomial viele in S. Die meisten also sind nicht drin. Satz: Falls es eine NP-schwierige duenn besetzte Menge S gibt, so ist P=NP. Beweis: Sei <, <= die lexikographische Ordnung auf {x in {0,1}^* | |x|<=n} fuer festes n. Wir haben fuer n=3 die Anordnung epsilon < 0 < 00 < 000 < 001 < 01 < 010 < 011 < 1 < 10 < 100 < 101 < 11 < 110 < 111. Denkt man sich diese Woerter als Knoten des vollstaendigen binaeren Baums, so werden sie in der Reihenfolge angeordnet, in der sie von der Tiefensuche besucht werden. Es sei LeftSAT = {(F,a) | F ist Formel in den n Variablen x1..xn und a ist in {0,1}^* mit i := |a| <= n und es existiert b mit a<=b und F(b)=1}. LeftSAT ist NP vollstaendig und somit gibt es eine FP Funktion g mit (F,a) in LeftSAT gdw. g(F,a) in S. Wir betrachten folgenden Algorithmus fuer SAT. input Formel F in n Variablen x1..xn; T := {epsilon}; for i = 1 .. n do T:=Extend(T); end if T enthaelt Belegung, die F erfuellt then accept else reject Hier ist Extend eine noch zu bestimmende Funktion mit den folgenden Eigenschaften: 1) Falls T eine Teilmenge von {0,1}^i fuer ein iaia' und F(b')=1. Da aber a Anfangsstueck von b mit b>=b' ist folgt a' (g(F,aj):S => g(F,ai):S) nach Definition von g. Somit liegen die g-Werte der ai alle in S bis zu einem bestimmten Punkt ab dem sie alle nicht mehr in S liegen. Formal: es gibt i0 sodass i<=i0 => g(F,ai):S und i>=i0 => g(F,ai) nicht in S. Die Moeglichkeit, dass alle g(F,ai) nicht in S sind (also quasi i0=-1) scheidet aus, da ja auf jeden Fall g(F,a):S). Da nun alle g-Werte voneinander verschieden sind (das war ja der Zweck des Blocks 4-6) muss i0<=p(q(|F|)) sein. Entfernen der ai mit i>p(q(|F|)) macht also nichts aus. * * * Anschliessend haben wir das Problem "Equivalent Formulas" eingefuehrt: EF = {(F,k) | F ist Boole'sche Formel, k natuerliche Zahl und F ist aequivalent zu einer Formel mit <= k Vorkommen von Literalen. } Es wurde gezeigt, dass SAT <= EF. Zu gegebener Formel F bestimmt man CNF F' sodass F erfuellbar gdw F' erfuellbar (das geht in polynomialer Zeit, siehe Uebung in BC). Dann schaut man, ob F' Tautologie ist (geht auch in polynomialer Zeit; man muss nur sehen, ob jede Klausel x und ~x fuer eine Variable x enthaelt.) Falls ja => erfuellbar, falls nein => erfuellbar, gdw (F',0) in EF. 25.11. EF ist in NP^SAT, da man ja die aequivalente Formel nichtdeterministisch raten kann und dann mit dem SAT-Orakel feststellen ob tatsaechlich Aequivalenz vorliegt. Definition der Polynomialen Hierarchie. Sigma0=Pi0=Delta0=P Sigman+1 = NP^Sigman Pin+1 = co-Sigman+1 Deltan+1 = P^Sigman PH = Vereinigung der Sigman Alternative Definition ueber polynomial beschraenkte Quantoren: L in Sigman gdw ex Polynom p und B in P sodass L = {x | Ey1Ay2Ey3...Qyn.(x,y1,...,yn) in B} hier bedeuten Ez: es gibt z mit |z|<=p(|x|) Az: fuer alle z mit |z|<=p(|x|) Qz: Ez oder Az je nachdem ob n ungerade oder gerade. Der Beweis dass die beiden Formulierungen aequivalent sind erfolgt durch Induktion ueber n. Fuer die schwierigere Richtung quantifiziert man existentiell ueber die moeglichen Orakelantworten und nichtdeterministischen Entscheidungen. Details siehe Buch. 2.12. Wir haben den Aequivalenzbeweis nochmal detailliert wiederholt und komplettiert. Die Frage kam auf, ob alle berechenbaren Probleme in die PH fallen. Antwoirt: Nein, da PH in EXP = Vereinigung der DTIME(2^p(n)) fuer p ein Polynom ist. Nach dem Zeithierarchiesatz ist aber EXP echt enthalten in 2EXP=DTIME(2^2^p(n)). Das Problem k-QBF ist Sigmak vollstaendig. Eine Instanz ist gegeben durch eine Boolesche Formel in der alle freien BooleschenVariablen entweder universell oder existentiell quantifiziert sind. Es duerfen nur hoechstens k Wechsel der Quantorenart stattfinden und der erste Quantor muss ein Existenzquantor sein. Die Frage ist dann, ob so eine quantifizierte Boolesche Formel wahr ist. Man weiss nicht, ob Sigmak echt in Sigmak+1 enthalten ist fuer alle k. Ist aber Pik enthalten in Sigmak, so gilt Sigman+1 = Sigman fuer alle n>=k. Unter der Annahme kann man naemlich zwei Quantoren vertauschen und damit die Zahl der Quantorenwechsel um eins reduzieren. Man sagt, SAT habe polynomiale Schaltkreise, kurz SAT in P/poly, falls es eine Familie von logischen Schaltkreisen C_n (aus UND ODER NICHT aufgebaut) gibt (wobei n in N) und ein Polynom p sodass |C_n|<= p(n) (Die Laenge |C_n| des Schaltkreises C_n bezieht sich auf eine vernuenftige Codierung von Schaltkreisen als 0-1-Woerter.) und ausserdem, das ist das wichtigste, soll C_n das SAT Problem fuer alle Formeln der Laenge phi loesen, d.h., falls |phi|<=n, so ist C_n(phi)01 gdw phi in SAT. C_n(phi) soll heissen, dass die Inputdraehte gemaess der Bits einer 01-Codierung von phi besetzt werden. In der Uebung beweisen Sie, dass SAT in P/poly gdw SAT in P^S fuer duenn besetzte Sprache S. Satz von Karp-Lipton: Falls SAT in P/poly, so ist Pi2 in Sigma2 enthalten. Beweis: Wegen der Vollstaendigkeit von k-QBF genuegt es zu zeigen, dass folgendes Problem in Sigma2 liegt: Gegeben phi(y,z) Boole'sche Formel, y,z Vektoren Boole'scher Variablen. Entscheide ob All y.Ex z.phi(y,z). Letzteres ist aequivalent zu All y."phi(y,-) in SAT". phi(y,-) ist die Formel, in der die ersten Variablen vorbesetzt sind und die zweite Garnitur frei bleibt. Wenn nun SAT in P/poly, dann gibt es fuer jedes n auch einen Schaltkreis D_n, der eine erfuellende Belegung ausgibt falls die Eingabe in SAT ist und diese Tatsache nicht nur anzeigt (Stichwort, Selbstreduzierbarkeit von SAT, binaere Suche). Wenn |psi| <= n so ist also psi(D_n(psi)) = 1 gdw psi in SAT. Es gilt: All y."phi(y,-) in SAT" genau dann wenn Ex D.All y.phi(y,D(phi(x,y,-)))=1 hier ist D ein Vektor von Boole'schen Variablen der Laenge p(n) wobei n>=|phi(y,-)| unabhaengig von y. Diese Variablen D sollen einen Schaltkreis codieren: D(phi...) bedeutet strenggenommen, dass die Decodierung von D auf die Codierung von phi... angewandt wird. Man mache sich die beiden Richtungen des "genau dann wenn" klar: Eine Richtung verwendet eben SAT in P/poly, die andere Richtung folgt unmittelbar aus der Definition von SAT. Wenn phi(y,irgendein wilder Ausdruck)=1, so ist phi(y,-) in SAT. 6.12 - 13.1. Die Eintraege vom 9.12. und 16.12 sind verlorengegangen. Behandelt wurden Kapitel 8: 8.1-8.5, also Der Satz von Hopcroft et al ueber die Crossing Sequenzen, der Satz von Savitch, der Satz von Immerman Szelepcsenyi. Ausserdem wurde das Theorem von Cook bewiesen, demzufolge DSPACE(s(n))+STACK = DTIME(2^(s(n))) ist, sobald s(n)>log(n). Fuer den Beweis verweise ich auf die Originalarbeit, oder das Buch von Wagner-Wechsung. Vielleicht schreibe ich ihn auch bei Gelegenheit hier auf, aber nicht jetzt. Das Platzhierarchietheorem wurde in der Form DSPACE(s(n)) echt enthalten in DSPACE(n.s(n)) erwaehnt, sofern s(n) ein vernuenftige Funktion ist, z.B ein Polynom. Sodann wurde Kapitel 8.6 ueber PSPACE behandelt und sodann 8.5 (LOGSPACE) aber noch ohne den Abschnitt ueber P-vollstaendige Probleme. Als Illustration des Satzes von Cook wurde die von mir entwickelte Programmiersprache LFPL vorgestellt. Fuer Details, die auch fuer die dritte Hausaufgabe relevant sind verweise ich auf http://www.dcs.ed.ac.uk/home/resbnd/prototypes/Borel/ 20.1. Ausgefallen 27.1. P-vollstaendigkeit von "Solvable Path Systems". Motivation, dass Solvable Path Systems *nicht* in NLOGSPACE sein sollte vermittels Pebblezahl. Genauer gesagt wurde folgendes gezeigt: Betrachte folgenden Nichtdeterministischen Algorithmus fuer SPS: n the number of nodes ("facts"), d a parameter A = {s} While t not in A and elapsed time <= n do guess x,y in A and rule r=(x,y,z) in R. A = A u {z} if |A| > d then guess u in A; A = A \ {u} if t in A accept else reject. Es gibt eine Familie von Instanzen von SPS sodass d=Omega(Wurzel-aus-n) erforderlich ist, damit dieser Algorithmus funktioniert. D.h. also insbesondere, dass es kein festes d (von n unabhaengig) gibt, sodass dieser Algorithmus korrekt waere und somit kein NLOGSPACE Verfahren existiert, was darauf basieren wuerde, dass man Regeln raet und ein paar schon gezeigte Facts vorhaelt. Wenn's ueberhaupt in NLOGSPACE geht, dann muesste es also ein ziemlich cleveres Verfahren sein. Eine Moeglichkeit, die Omega(sqrt(n)) Schranke zu realisieren, ergibt sich bei Instanzen der Form . . . . \ / \ / \ / . . . \ / \ / . . \ / t hier sollen die Punkte paarweise verschiedene Facts symbolisieren und eine Konfiguration a b \ / c symbolisiert eine Regel (a,b,c). Zusaetzlich gibts Regeln der Form (s,s,x) wobei x die Facts der ersten Reihe durchlaeuft. Den obigen Graphen kann man versuchen zu "pebbeln" nach der folgenden Vorschrift: Man darf jederzeit ein Pebble auf einen Knoten der ersten Reihe legen. Liegen auf den Knoten a,b einer Konfiguration a b \ / c schon Pebbles, dann darf man die wegnehmen und stattdessen ein Pebble auf c legen. Man ist fertig, wenn ein Pebble auf t liegt. Die Weggenommenen darf man natuerlich wiederverwenden. Die Frage ist, wieviele Pebbles man hier braucht, also wie viele zu einem Zeitpunkt gleichzeitig im Einsatz sein muessen. Durch Induktion sieht man leicht, dass soviele Pebbles erforderlich sind, wie die unterste Schicht breit ist, also Omega(sqrt(n)), wenn n die Zahl aller Knoten ist. Das Konzept der Pebblezahl (Minimum erforderlicher Pebbles) hat naheliegende Bezuege zur Minimalzahl von Registern, die zur Auswertung eines arithm Ausdrucks der Groesse n noetig sind. Man weiss, dass die Pebblezahl eines beliebigen DAGs (directed acyclic graph) der Groesse n ein O(n/log(n)) ist. Daruas ergibt sich auch sofort DTIME(t(n)) enthalten in DSPACE(t(n) / log(t(n))). Siehe Schoening:Perlen der theoret. Informatik. * * * * * * * * * * * * * * * * * * * * * * * * * * * Definition der probabilistischen polytime Turingmaschine nach Bovet-Crescenzi, probabilistische Komplexitaetsklassen PP, BPP und IP. Als Beispiel vorgefuehrt, dass das Komplement von Graphisomorphismus in IP ist. 3.2. Wdh der Definition von IP. Beweis dass ein Orakel A existiert, sodass co-NP^A nicht enthalten in IP^A ist. Beweis, dass aber trotzdem co-NP enthalten in IP ist durch Angabe eines expliziten IP-Protokolls fuer das Kompelement von 3SAT basierend auf einer Kodierung von log. Formeln durch Polynome.