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.                    

         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.