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