Event Detail

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