A model-theoretic characterization of the weak pigeonhole principle

DOI10.1016/S0168-0072(02)00038-6zbMath1008.03024MaRDI QIDQ1849868

Neil Thapen

Publication date: 2 December 2002

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

cryptographybounded arithmeticmodels of arithmeticcomplexity theoryweak pigeonhole principleabstract model theory

Mathematics Subject Classification ID

Cryptography (94A60) First-order arithmetic and fragments (03F30) Nonstandard models of arithmetic (03H15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Models of arithmetic and set theory (03C62) Complexity of proofs (03F20) Categoricity and completeness of theories (03C35) Abstract model theory (03C95)

Related Items (13)

Dual weak pigeonhole principle, Boolean complexity, and derandomization ⋮ Approximate counting and NP search problems ⋮ Circuit principles and weak pigeonhole variants ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ The Ordering Principle in a Fragment of Approximate Counting ⋮ The polynomial and linear hierarchies in models where the weak pigeonhole principle fails ⋮ A note on the Σ₁collection scheme and fragments of bounded arithmetic ⋮ Where pigeonhole principles meet Koenig lemmas ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Upper and lower Ramsey bounds in bounded arithmetic ⋮ Structures interpretable in models of bounded arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classification theory over a predicate. I
• \(\aleph_0\)-categoricity over a predicate
• A uniform approach to define complexity classes
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Relating the bounded arithmetic and polynomial time hierarchies
• Uniform Families of Polynomial Equations Over a Finite Field and Structures Admitting an Euler Characteristic of Definable Sets
• Closure properties of countable non-standard integers
• A method for obtaining digital signatures and public-key cryptosystems
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings
• Notes on polynomially bounded arithmetic
• A new proof of the weak pigeonhole principle

This page was built for publication: A model-theoretic characterization of the weak pigeonhole principle