PředmětyPředměty(verze: 837)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Důkazová složitost a P vs. NP problém - NMAG536
Anglický název: Proof Complexity and the P vs. NP Problem
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2019
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: angličtina
Způsob výuky: prezenční
Další informace: http://www1.karlin.mff.cuni.cz/~krajicek/ds11.html
Garant: prof. RNDr. Jan Krajíček, DrSc.
Třída: M Mgr. MSTR
M Mgr. MSTR > Povinně volitelné
Kategorizace předmětu: Matematika > Algebra
Neslučitelnost : NALG139
Záměnnost : NALG139
Anotace -
Poslední úprava: T_KA (14.05.2013)
Přednáška se bude zabývat tzv. Cookovým programem, který redukuje P vs. NP problém na úkol dokazat spodní odhady na délky výrokových důkazů. I částečné pokroky v tomto programu maji řadu důsledků (např. pro automatické dokazování či v matematické logice).
Podmínky zakončení předmětu - angličtina
Poslední úprava: prof. RNDr. Jan Krajíček, DrSc. (06.02.2018)

Oral exam: see http://www.karlin.mff.cuni.cz/~krajicek/zk-ds.html.

Literatura -
Poslední úprava: T_KA (14.05.2013)

J. Krajíček: "Bounded arithmetic, propositional logic, and complexity theory", Encyclopedia of Mathematics and Its Applications, Vol.60, Cambridge University Press, (1995).

P. Pudlák: The lengths of proofs, in Handbook of Proof Theory, S.R. Buss ed., Elsevier, 1998, pp.547-637.

Sylabus -
Poslední úprava: T_KA (14.05.2013)

Přednáška se bude zabývat tzv. Cookovým programem, který redukuje P vs. NP problém na úkol dokazat

spodní odhady na délky výrokových důkazů. I částečné pokroky v tomto programu maji řadu důsledků (např.

pro automatické dokazování či v matematické logice).

 
Univerzita Karlova | Informační systém UK