An Isaac Newton Institute Workshop

New Directions in Proof Complexity

T^1_2, T^2_2 and search problems

Author: N Thapen (Academy of Sciences, Prague)

Abstract

We give some new, natural principles characterizing the \Sigma^b_1 consequences of these theories, based on a reflection principle for resolution.