
Jan Krají?ek

(Charles University)

Proof Complexity Catch 22
 Abstract:

I will present some views on the structure of proof complexity and possible research directions, illustrating them by some theorems and problems.

Pavel Pudlák

(IM CAS)

A proof system polynomially equivalent to bounded depth Frege, part 3
 Abstract:

In the 3rd part we will show how to reduce the disjoint NP pairs of the games we introduced in the 2nd part to the canonical pairs of bounded depth Frege systems. To this end we will use the proof system equivalent to bounded depth Frege introduced in the 1st part. Given a refutation of A(x) & B(y) in this system, we will define a game and show that a satisfying assignment for A(x) (resp. B(y)) can be transformed into a positional winning strategy for Player I (resp. II).
Pavel Pudlak, Neil Thapen
organizers