Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
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).
Předmět nemusí být vyučován každý rok.
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
The course is concerned with the so called Cook's
program which reduces the P vs. NP problem to the
task to
prove lengths-of-proofs lower bounds for
propositional proofs. Even partial advances in the program
have various
concequences (e.g. for automated theorem
proving or in mathematical logic).
The course may not be taught every academic year.
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: prof. RNDr. Jan Krajíček, DrSc. (26.02.2024)
J. Krajíček: "Bounded arithmetic, propositional logic, and complexity theory", Encyclopedia of Mathematics and Its Applications, Vol.170, Cambridge University Press, (2019).
Poslední úprava: prof. RNDr. Jan Krajíček, DrSc. (26.02.2024)
J. Krajíček: "Bounded arithmetic, propositional logic, and complexity theory", Encyclopedia of Mathematics and Its Applications, Vol.170, Cambridge University Press, (2019).
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).
Poslední úprava: T_KA (14.05.2013)
The course is concerned with the so called Cook's program which reduces the P vs. NP problem to the
task to prove lengths-of-proofs lower bounds for propositional proofs. Even partial advances in the program
have various concequences (e.g. for automated theorem proving or in mathematical logic).