This is a five days course I'll teach at University of Salerno from March 30 to April 3.
The course is intended for PhD students not expert in Proof Complexity.
It is organized in such a way of presenting motivations, proof techniques and results
for the case of Resolution and only the last two daysgive a quick look into other
proof systems motivating there the same problems seen for Resolution.
I'll keep posting the pdf of the slides.
Monday 30
Organization
Informal Introduction (In Italian. Slides drawn from a previous talk at the Faculty of Science at "La Sapienza")
First steps in Proof Complexity
Tuesday 31
Exponential Separation between treelike and daglike Resolution
Wednesday 1
Lower bounds for dagike Resolution
Thursday 2
Other measures and methods for Resolution
Friday 3
Other proof systems
Books and Lecture Notes
P. Beame. Proof Complexity. IAS Summer School.
P. Beame, T. Pitassi. Propositional Proof Complexity: Past, Present and Future. Bullettin of the EATCS 65:66-89, 98.
S. Buss. Lectures on Proof theory . Mc Gill University
P. Clote, E. Kranakis. Boolean functions and Computation Models. Springer, 2002.
J. Krajíček. Bounded Arithmetic, Propositional Logic
and
Complexity Theory.
J. Krajíček. Propositional
Proof Complexity (lecture notes).
N. Segerlind. The complexity of Propositional proofs
Others similar courses
Prof. T. Pitassi:
Prof. S. Cook. University of Toronto:
Proof
Complexity and Bounded Arithmetic (2002)
Workshop e
Schools
Prague Fall school on
Logic and Complexity (J. Krajicek)
NoNa summer School on Complexity Theory