Tutorial talks:
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.
Abstract:
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.