test FOO test

**Computability in Europe 2006**

Logical Approaches to Computational Barriers

### 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 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.

websites: Arnold Beckmann |
2006-07-19 |