Samuel R. Buss
"Proof Complexity and Computational Hardness''.
Transparencies for three tutorial lectures.
Conference on Computability in Europe (CiE), held June-July 2006.
Talks given July 3, July 4 and July 5, 2006.
Download: postscript or PDF.
Day 1: Proof Complexity and Feasible Computation Classes. Introduction to proof complexity. Cook's program for P versus NP. Automatizability. Hardness of automatizability based on hardness of factoring Blum integers. Craig interpolation.
Day 2: Bounded Arithmetic and Propositional Proofs. Discussion of bounded arithmetic. The Paris-Wilkie translation. Proofs of the witnessing theorems for S^1_2 and T^1_2 in terms of polynomial time and polynomial local search (PLS).
Day 3: On the lack of progress towards P versus NP. The state of the art in "logical" attempts to prove P is not equal to NP.
Back to Sam Buss's publications page.