INFORMATIKAI KAR DOKTORI PROGRAM
SZIGORLATI TEMATIKA

Bonyolultságelmélet


A Turing-gép. Az univerzális Turing-gép definiciója és létezése. A k-szalagos Turing gép szimulálható 1 szalagossal O(N^2)idõben. A RAM-gép. Rekurzív és rekurzíve felsorolható nyelvek. Idõ-és tárkorlátos nyelvosztályok. DSPACE(f(n)), DTIME(f(n)),P,PSPACE. Lineáris gyorsítási tétel. Minden rekurzív f függvényhez létezik olyan rekurzív nyelv, amely nincs benne DTIME(f(n))-ben (azaz tetszõlegesen nehéz nyelv van).

A nem-determinisztikus Turing-gép. Nem-determinisztikus nyelvosztályok.

NP-teljesség definícíója. Cook tétele: A SAT NP-teljes
Véletlen algoritmusok, Véletlen komplexitásosztályok, randomizált Turing-gép. Véletlen algoritmus teljes párosítás létezésének eldöntésére páros gráfban. Prímtesztek: gyenge próbálkozások, Fermat-teszt, Miller-Rabin - teszt. Az Agrawal-Kayal-Saxena teszt: a prímek P-ben vannak (bizonyítás nélkül).

LOGSPACE, NLOGSPACE. ELÉRHETÕSÉG NLOGSPACE-ben van, PALINDROMÁK LOGSPACE-ben. ELÉRHETÕSÉG benne van DSPACE( log^2 n)-ben. Savitch tétele. PSPACE-teljesség, a TQBF nyelv.
Interaktív játékok és bizonyítások (Babai, Micali, Rackoff). Az IP osztály. Shamir tétele: IP=PSPACE. Kommunikációs játékok, a Mehlhorn-Schmidt tétel. Nem-determinisztikus kommunikációs bonyolultság. Randomizált kommunikációs játékok. Az Aho-Ullman-Yannakakis tétel Boole-hálózatok: méret, mélység, be-fok. Uniform és nem-uniform AC és
NC. Korlátos mélységû Boole-hálózatok. A Yao-Hastad tétel.
Párhuzamos számítógépek, PRAM. Elemkülönbözõség konstans idõben. MAX számítás n^2 és n processzorral is. Rendezés n processzorral O(\log^2 n) idõben. Skalárszorzat, mátrixszorzás párhuzamosan. Súlyozott élû gráfban minden csúcspár közötti legrövidebb utak számítása párhuzamosan. A Brent-elv; alkalmazás ha kevesebb processzorunk van.


Irodalom:

Lovász László: Algoritmusok bonyolultsága, jegyzet (az 1992, vagy az utáni kiadások).
Papadimitriou: Algoritmusok bonyolultsága, (egyetemi tankönyv) Novadat, 1999.