๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A model-theoretic characterization of the weak pigeonhole principle

โœ Scribed by Neil Thapen

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
196 KB
Volume
118
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

โœฆ Synopsis

We bring together some facts about the weak pigeonhole principle (WPHP) 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 + (sharply bounded collection for PV formulas) lies strictly between PV and S 1 2 in strength, assuming that the cryptosystem RSA is secure.

๐Ÿ“œ SIMILAR VOLUMES

A New Proof of the Weak Pigeonhole Princ
A New Proof of the Weak Pigeonhole Principle
โœ Alexis Maciel; Toniann Pitassi; Alan R. Woods ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 213 KB

The exact complexity of the weak pigeonhole principle is an old and fundamental problem in proof complexity. Using a diagonalization argument, J. B. Paris et al. (J. Symbolic Logic 53 (1988), 1235-1244) showed how to prove the weak pigeonhole principle with bounded-depth, quasipolynomialsize proofs.

Resolution lower bounds for the weak fun
Resolution lower bounds for the weak functional pigeonhole principle
โœ Alexander A. Razborov ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 243 KB

We show that every resolution proof of the functional version FPHP m n of the pigeonhole principle (in which one pigeon may not split between several holes) must have size exp( (n=(log m) 2 )). This implies an exp( (n 1=3 )) bound when the number of pigeons m is arbitrary.

A characterization of the extension prin
A characterization of the extension principle
โœ Ronald R. Yager ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 507 KB

We provide an alternative characterization of the extension principle of fuzzy sets. This characterization is based upon using relations to represent mappings. We apply this new characterization to develop an extension for non-deterministic mappings.