Proof Complexity

Lecturer: 
Topic: 
Logic & Computation
Level: 
Introductory
Abstract: 

The aim of this course is to present an up-to-date introduction to propositional proof complexity with emphasis on connections to SAT solving and game-theoretic techniques. The course will start with a gentle introduction to the complexity of theorem proving and its relations to central questions in computational complexity. We will cover important proof systems, current knowledge about proof lengths in these systems, and implications for the performance of satisfiability algorithms. We will also provide an overview of proof complexity results for non-classical logics as modal, intuitionistic and quantified boolean formulas and their relations to QBF solving.

Week: 
Second week
Slot: 
11:00 - 12:30 - slot 2
Room: 
52.019