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 (03.03.2011)
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).
Literatura -
Poslední úprava: T_KA (03.03.2011)
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.
Poslední úprava: T_KA (03.03.2011)
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 (03.03.2011)
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 (03.03.2011)
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).
