An Isaac Newton Institute Workshop

New Directions in Proof Complexity

When can $S^1_2$ prove the weak pigeonhole principle?

Author: C Pollett (San Jose State University)

Abstract

It is well known result of Krajicek and Pudlak that if $S^1_2$ could prove the injective weak pigeonhole principle for every polynomial time function then RSA would not be secure. In this talk, we will consider function algebras based on a common characterization of the polynomial time functions where we slightly modify the initial functions and further restrict the amount of allowable recursion. We will then argue that $S^1_2$ can prove the surjective weak pigeonhole principle for functions in this algebra.