Dukazova slozitost
Rozsah: 2/0. Prednasky je treba zapsat zvlast: obe budou zakonceny zkouskou. Je mozno zapsat i jen jednu z nich.
(LS 2003, kod TIN068)
Dukazova slozitost a aritmetika
(ZS 2003, kod TIN069)
Cas a misto (podzim'03): ctvrtek 13.oo - 14.3o, MU (Zitna 25, Praha 1), seminarni mistnost v prizemi (tzv.konirna).
Jan Krajicek
Dukazova slozitost je oblast spojujici matematickou logiku a teorii vypocetni slozitosti. Zakladnimi problemy jsou vztahy trid P, NP a coNP. Konkretni problem je tento: Existuje dukazovy system v nemz ma kazda vyrokova tautologie kratky (polynomialni ci alespon subexponencialni) dukaz? Obecny "dukazovy system" je proste nedeterministicky algoritmus prijimajici prave vyrokove tautologie (obvykle formalni systemy lze chapat jako "dukazove systemy" v tomto smyslu). Tato otazka je ekvivalentni problemu, je-li trida NP uzavrena na doplnky. Cilem je ukazat, ze takovy dukazovy system neexistuje: chceme dokazat spodni odhady na delky dukazu (t.j. na nedeterministicky cas) ve vsech moznych dukazovych systemech. Planuji vylozit, co se v teto oblasti vi a co jsou zajimave smery soucasneho vyzkumu.
V prednasce "Dukazova slozitost" proberu nejdulezitejsi zname spodni odhady. Tato prednaska bude do znacne miry kombinatoricka.
V prednasce "Dukazova slozitost a aritmetika" se zamerim na temata, ktera mi pripadaji nadejna pro dalsi rozvoj a ktera maji hlubsi souvislost s matematickou logikou.
Druhou prednasku lze zapsat (a sledovat) i bez absolvovani prvni.
Posluchac prednasek by mel za sebou mit, idealne, zakladni kursy matematicke logiky (predikatovy pocet, formalni aritmetika,...) a vypocetni slozitosti (NP-uplnost, booleovske obvody). Nicmene, motivovany student se muze veci doucit, jak budou potreba. Zejmena prvni prednaska nebude vyzadovat moc znalosti z logiky.Sylabus:
Sylabus prednasek bude mit urcity prunik s mymi prednaskami v Oxfordu'97 a '99, ale bude obsahovat i zcela nove veci. Prubezne s prednaskami napisi strucna skripta, ktera budou k dispozici posluchacum.