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 2023
• 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: nevyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• 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
• Je záměnnost pro: NALG139

Anotace

čeština

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.

angličtina

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

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

čeština

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

čeština

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

angličtina

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