test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
An up-to-date version of the presentation can be found
Day 1: Proof Complexity
and Feasible Computation Classes.
proof complexity. Cook's program for P versus NP.
Automatizability. Hardness of automatizability based on hardness
factoring Blum integers. Craig interpolation.
Day 2: Bounded Arithmetic
and Propositional Proofs.
bounded arithmetic. The Paris-Wilkie translation. Proofs
witnessing theorems for S12
and T12 in terms of polynomial
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