Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 266)
Detail práce
   Přihlásit přes CAS
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.
 
Univerzita Karlova | Informační systém UK