Důkazová složitost a P vs. NP problém - NALG139

• 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
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: zrušen
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Další informace: http://www.karlin.mff.cuni.cz/~krajicek/ds11.html
• Garant: prof. RNDr. Jan Krajíček, DrSc.
• Kategorizace předmětu: Matematika > Algebra
• Záměnnost : NMAG536
• Je neslučitelnost pro: NMAG536
• Je záměnnost pro: NMAG536

Anotace

čeština

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)

angličtina

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).

Poslední úprava: T_KA (03.03.2011)

Literatura

čeština

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)

Sylabus

čeština

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)

angličtina

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).

Poslední úprava: T_KA (03.03.2011)