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: T_KA (14.05.2013)
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. |
|
||
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).
|