Logic Colloquium: Combinatorial principles from proof complexity

Colloquium | October 12 | 4-5 p.m. | 60 Evans Hall

 Pavel Pudlak, Czech Academy of Sciences

 Department of Mathematics

One of the goals of proof theory is to find combinatorial characterization of sentences provable in particular theories, i.e., to present these sentences as mathematical principles, rather than mere syntactical statements. While for strong theories these sentences tend to be incomprehensible, for weak theories we expect to find something familiar, or at least similar to well-known principles. In this talk I will report on the project to characterize provably disjoint NP pairs of sets in systems called Bounded depth Frege systems. The resulting characterization is expressed in terms of positional strategies in some combinatorial games that generalize the standard concept of a finite game.

 pierre.simon@berkeley.edu