A model-theoretic characterization of the weak pigeonhole principle

Annals of Pure and Applied Logic 118 (1-2):175-195 (2002)
  Copy   BIBTEX

Abstract

We bring together some facts about the weak pigeonhole principle from bounded arithmetic, complexity theory, cryptography and abstract model theory. We characterize the models of arithmetic in which WPHP fails as those which are determined by an initial segment and prove a conditional separation result in bounded arithmetic, that PV + lies strictly between PV and S21 in strength, assuming that the cryptosystem RSA is secure

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(02)00038-6

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,225

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

Structures interpretable in models of bounded arithmetic.Neil Thapen - 2005 - Annals of Pure and Applied Logic 136 (3):247-266.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
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.
The weak pigeonhole principle for function classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
Dual weak pigeonhole principle, Boolean complexity, and derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
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.
Models of Bounded Arithmetic Theories and Some Related Complexity Questions.Abolfazl Alam & Morteza Moniri - 2022 - Bulletin of the Section of Logic 51 (2):163-176.
A Model‐Theoretic Property of Sharply Bounded Formulae, with some Applications.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (2):205-215.
Approximate counting and NP search problems.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2022 - Journal of Mathematical Logic 22 (3).
Abelian groups and quadratic residues in weak arithmetic.Emil Jeřábek - 2010 - Mathematical Logic Quarterly 56 (3):262-278.

Analytics

Added to PP
2014-01-16

Downloads
23 (#938,419)

6 months
5 (#1,037,427)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Dual weak pigeonhole principle, Boolean complexity, and derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
Structures interpretable in models of bounded arithmetic.Neil Thapen - 2005 - Annals of Pure and Applied Logic 136 (3):247-266.

View all 8 citations / Add more citations

References found in this work

Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
Classification theory over a predicate. I.Anand Pillay & Saharon Shelah - 1985 - Notre Dame Journal of Formal Logic 26 (4):361-376.
[Symbol] o-categoricity over a predicate.Anand Pillay - 1983 - Notre Dame Journal of Formal Logic 24:527-536.

Add more references