The weak pigeonhole principle for function classes in S12

&
Mathematical Logic Quarterly 52 (6):575-584 (2006)
  Copy   BIBTEX

Abstract

It is well known that S12 cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability of the surjective weak pigeonhole principle in S12 for provably weaker function classes

Categories

Add categories

Keywords

Reprint years

DOI

10.1002/malq.200610015

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,252

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

A note on the E1 collection scheme and fragments of bounded arithmetic.Zofia Adamowicz & Leszek Aleksander Kołodziejczyk - 2010 - Mathematical Logic Quarterly 56 (2):126-130.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
Abelian groups and quadratic residues in weak arithmetic.Emil Jeřábek - 2010 - Mathematical Logic Quarterly 56 (3):262-278.
An induction principle and pigeonhole principles for k-finite sets.Andreas Blass - 1995 - Journal of Symbolic Logic 60 (4):1186-1193.
Witnessing functions in bounded arithmetic and search problems.Mario Chiari & Jan Krajíček - 1998 - Journal of Symbolic Logic 63 (3):1095-1115.
Matrix identities and the pigeonhole principle.Michael Soltys & Alasdair Urquhart - 2004 - Archive for Mathematical Logic 43 (3):351-357.
Pigeonhole and Choice Principles.Wolfgang Degen - 2000 - Mathematical Logic Quarterly 46 (3):313-334.
Isols and the pigeonhole principle.J. C. E. Dekker & E. Ellentuck - 1989 - Journal of Symbolic Logic 54 (3):833-846.
A model-theoretic characterization of the weak pigeonhole principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.
Dual weak pigeonhole principle, Boolean complexity, and derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
The polynomial and linear hierarchies in models where the weak pigeonhole principle fails.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2008 - Journal of Symbolic Logic 73 (2):578-592.
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds.Jan Kraj�?Ek - 2004 - Journal of Symbolic Logic 69 (1):265-286.

Analytics

Added to PP
2013-12-01

Downloads
17 (#824,750)

6 months
2 (#1,182,310)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Structure and definability in general bounded arithmetic theories.Chris Pollett - 1999 - Annals of Pure and Applied Logic 100 (1-3):189-245.
Dual weak pigeonhole principle, Boolean complexity, and derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
On the bounded version of Hilbert's tenth problem.Chris Pollett - 2003 - Archive for Mathematical Logic 42 (5):469-488.

Add more references