Primtesztelés, amely mindig mûködik: A Rabin-Miller teszt.
Titkosírások, titkos kulcsú, nyilvános kulcsú titkosírások. A vektorok mod 2 koordinátánkénti összeadására alapozott titkosírás. Az RSA titkosírás. A kiterjesztett euklideszi algoritmus.
Újabb véletlen algoritmusok: a polinomegyenlõség ellenõrzése, a Schwartz-lemma.
Kommunikációs játékok,
determinisztikus kommunikációs bonyolultság, a
Mehlhorn-Schmidt tétel.
A nem-determinisztikus kommunikációs bonyolultság jellemzése fedõ téglalapokkal. Rabin és Simon véletlent használó protokollja.
VLSI-tervezés, Thompson tétele.
A számítógépek egy absztrakt modellje: A Turing-gép.Példák Turing-gépre.
Church tézis. A palindrómák, ezeket elfogadó 1 és 2 szalagos Turing-gép.
Az univerzális Turing gép definiciója és létezése.
k-szalagos Turing gép szimulálható 1
szalagossal O(N^2) lépésben.
Rekurzív és rekurzíve felsorolható nyelvek. Majdnem minden nyelv nem-rekurziv, és még csak nem is rekurzíve felsorolható.
A rekurziv - és rekurzíve felsorolható
nyelvek alapvetõ tulajdonságai. A megállási
probléma. Algoritmikusan eldönthetetlen, hogy egy
leirásával adott
Turing-gép egy inputon
leáll-e.
Idõ-bonyolultsági osztályok. A P osztály.
Artúr-Merlin játék. Az NP-osztály.
co-NP. Példák NP-beli nyelvekre.
A PRIM nyelv, Pratt tétele (bizonyítás nélkül). Polinomiális redukció, NP-teljesség.
Boole-formulák. A SAT nyelv.
Cook tétele: a SAT NP-teljes.
További NP-teljes nyelv: LEFOG.