Proof Complexity and the P vs. NP Problem - NMAG536
|
|
|
||
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
|
|
||
Last update: prof. RNDr. Jan Krajíček, DrSc. (06.02.2018)
Oral exam: see http://www.karlin.mff.cuni.cz/~krajicek/zk-ds.html. |
|
||
Last update: 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). |
|
||
Last update: 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).
|