Computability in Europe 2006
Logical Approaches to Computational Barriers
|Speaker:||Samuel R Buss|
An up-to-date version of the presentation can be found
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|