Computability in Europe 2006
Logical Approaches to Computational Barriers

Proof complexity and computational hardness

Speaker: Samuel R Buss


An up-to-date version of the presentation can be found here

         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 S12 and T12 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.

websites: Arnold Beckmann 2006-07-19