Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Tutorial:
Proof complexity and computational hardness

Speaker: Samuel R Buss
Presentation: talkslides.pdf

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 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net