Bonyolultságelmélet
Előadás IV-ed éves matematikusoknak
1997 tavasz
Hétfő 10-11:30, II.4.
Hirdetmények
- Közös megegyezésünk alapján az előadás 10-kor kezdődik.
- Vizsgázni természetesen majd az előadáson elhangzott anyagból kell!
-
Szeptemberben Friedl Kati vizsgáztat!
Vizsgára jelentkezni e-mail-ben
lehet!
Ajánlott irodalom
- Lovász László: Algoritmusok Bonyolultsága, jegyzet
- Hopcroft-Ullman: Introduction to Automata Theory, Languages, and Computation
1. előadás (II. 17.)
Turing gépek. Lineáris gyorsítás.
2. előadás (II. 24.)
Szimulálás kétszalagos Turing-géppel O(N.logN) időben. Univerzális Turing-gép.
Diagonilázálás, tár és idő-hierarchia tétel. Időkonstruálható és jól számolható
függvények. Hézag-tétel.
3. előadás (III. 3.)
Gyorsítási tétel, lezárási tétel (utóbbi csak kimondva).
Logspace visszavezethetoseg tranzitivitasa. PSPACE-teljesség, QBF.
4. előadás (III. 10.)
Létezik olyan A és B orákulum, hogy P^A=NP^A és P^B\ne NP^B.
Alternáló Turing-gépek és Alternáló hierarchia.
5. előadás (III. 17.) Varga Dániel
Szavazós játék. Gyenge és erős reprezentáció polinommal.
6. előadás (III. 24.) Varga Dániel
Ha van kis hibájú approximáció, akkor van "nem sokkal nagyobb fokú" gyenge
reprezentáció is. ÉS kapu approximációja kis hibával. Alsó becslés PARITÁS-ra.
6. előadás (IV. 7.)
Boole-hálózatok mélysége, formula-bonyolultság. Kommunikációs játék
relációkon, összefüggés előzőkkel. Alkalmazások, AKS sorting network,
szelet-függvény, Dunne és Krapchenko tételei, protokoll párosításra és
st-útra. Asszimmetrikus, fordulónkénti protokoll, st-útra alsó becslés.
8. előadás (IV. 14.) Ivanyos Gábor
Négyzetmentes polinomok faktorizációja.
Egy polinom három nézete. Minimális ideálok és
faktorok megfeleltetése. Berlekamp módszerei.
9. előadás (IV. 21.) Ivanyos Gábor
Gyökök közelítése a komplex számok felett. Sturm tétele.
Egész (racionális) együtthatós polinomok faktorizációja.
Zassenhaus p-adikus közelítéses módszere, Hensel lemma.
A. K. Lenstra ötlete. Az LLL bázisredukciós algoritmus közel legrövidebb
rácsvektor keresésére.
10. előadás (IV. 28.) Ivanyos Gábor, Friedl Katalin
Minimálpolinom kiszámítása bázisredukció segítségével.
(H. W. Lenstar jr., Lovász László, R. Kannan).
NP, SNP, MAXNP, MAXSNP. MAXSNP teljesség, pl. MAX3SAT teljes.
Minden MAXSNP-beli konstans faktoron belül közelíthető.
PCP és kapcsolata MAXSNP-vel.
11. előadás (V. 5.) Friedl Katalin
NP=PCP(O(log n),O(1)). Maximális klikk approximálhatatlansága 1/2-es
ill. konstans faktoron belül. Még n^c-n belül sem lehet (megfelelő c-re).
Ugyanez kromatikus számra.
11. előadás (V. 12.) Friedl Katalin
Interaktív bizonyítás, Arthúr-Merlin játék. co-NP része IP-nek.
IP=PSPACE (biz. nélkül). Több bizonyító, MIP=NEXP (biz. nélkül).