Proof Complexity and the P vs. NP Problem - NMAG536
|
|
|
||
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.
Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (14.05.2019)
|
|
||
Oral exam: see http://www.karlin.mff.cuni.cz/~krajicek/zk-ds.html. Last update: Krajíček Jan, prof. RNDr., DrSc. (06.02.2018)
|
|
||
J. Krajíček: "Bounded arithmetic, propositional logic, and complexity theory", Encyclopedia of Mathematics and Its Applications, Vol.170, Cambridge University Press, (2019). Last update: Krajíček Jan, prof. RNDr., DrSc. (26.02.2024)
|
|
||
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).
Last update: T_KA (14.05.2013)
|