Complexity theory in Feasible Mathematics
| Název práce v češtině: | Teória zložitosti v dosiahnuteľnej matematike |
|---|---|
| Název v anglickém jazyce: | Complexity theory in Feasible Mathematics |
| Klíčová slova: | booleovské obvody, obmedzená aritmetika, PCP veta |
| Klíčová slova anglicky: | Circuit Lower Bounds, Bounded Arithmetic, The PCP theorem |
| Akademický rok vypsání: | 2011/2012 |
| Typ práce: | disertační práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | prof. RNDr. Jan Krajíček, DrSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 26.09.2011 |
| Datum zadání: | 26.09.2011 |
| Datum potvrzení stud. oddělením: | 04.11.2011 |
| Datum a čas obhajoby: | 07.11.2014 11:00 |
| Datum odevzdání elektronické podoby: | 22.08.2014 |
| Datum odevzdání tištěné podoby: | 22.08.2014 |
| Datum proběhlé obhajoby: | 07.11.2014 |
| Oponenti: | prof. RNDr. Pavel Pudlák, DrSc. |
| prof. Samuel Buss | |
| Zásady pro vypracování |
| Prohloubit souvislosti mezi teorií složitosti a matematickou logikou. |
| Seznam odborné literatury |
| J.Krajíček,
"Bounded arithmetic, propositional logic, and complexity theory", Encyclopedia of Mathematics and Its Applications, Vol.60, Cambridge University Press, Cambridge - New York - Melbourne, (1995), 343pp. |