Computability in Europe 2006
Logical Approaches to Computational Barriers


Tutorial:
Proof complexity and computational hardness


Speaker: Samuel R Buss

Abstract

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