Skip to content



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

Pollett, C (San Jose State University)
Monday 10 April 2006, 16:00-16:30

Seminar Room 1, Newton Institute


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.


[ppt ]


MP3MP3 Real AudioReal Audio

Back to top ∧