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í
• 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

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: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (14.05.2019)

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). The course may not be taught every academic year.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (14.05.2019)

Podmínky zakončení předmětu

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

Poslední úprava: Krajíček Jan, prof. RNDr., DrSc. (06.02.2018)

Literatura

čeština

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

Poslední úprava: Krajíček Jan, prof. RNDr., DrSc. (26.02.2024)

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 (14.05.2013)

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 (14.05.2013)