# On the weak pigeonhole principle

Fundamenta Mathematicae (2001)

- Volume: 170, Issue: 1-2, page 123-140
- ISSN: 0016-2736

## Access Full Article

top## Abstract

top## How to cite

topJan Krajíček. "On the weak pigeonhole principle." Fundamenta Mathematicae 170.1-2 (2001): 123-140. <http://eudml.org/doc/282141>.

@article{JanKrajíček2001,

abstract = {We investigate the proof complexity, in (extensions of) resolution and in bounded arithmetic, of the weak pigeonhole principle and of the Ramsey theorem. In particular, we link the proof complexities of these two principles. Further we give lower bounds to the width of resolution proofs and to the size of (extensions of) tree-like resolution proofs of the Ramsey theorem.
We establish a connection between provability of WPHP in fragments of bounded arithmetic and cryptographic assumptions (the existence of one-way functions). In particular, we show that functions violating $WPHPₙ^\{2n\}$ are one-way and, on the other hand, one-way permutations give rise to functions violating $PHPₙ^\{n+1\}$, and strongly collision-free families of hash functions give rise to functions violating $WPHPₙ^\{2n\}$ (all in suitable models of bounded arithmetic).
Further we formulate a few problems and conjectures; in particular, on the structured PHP (introduced here) and on the unrelativised WPHP.},

author = {Jan Krajíček},

journal = {Fundamenta Mathematicae},

keywords = {proof complexity; resolution; bounded arithmetic; weak pigeonhole principle; Ramsey theorem; lower bounds; one-way functions},

language = {eng},

number = {1-2},

pages = {123-140},

title = {On the weak pigeonhole principle},

url = {http://eudml.org/doc/282141},

volume = {170},

year = {2001},

}

TY - JOUR

AU - Jan Krajíček

TI - On the weak pigeonhole principle

JO - Fundamenta Mathematicae

PY - 2001

VL - 170

IS - 1-2

SP - 123

EP - 140

AB - We investigate the proof complexity, in (extensions of) resolution and in bounded arithmetic, of the weak pigeonhole principle and of the Ramsey theorem. In particular, we link the proof complexities of these two principles. Further we give lower bounds to the width of resolution proofs and to the size of (extensions of) tree-like resolution proofs of the Ramsey theorem.
We establish a connection between provability of WPHP in fragments of bounded arithmetic and cryptographic assumptions (the existence of one-way functions). In particular, we show that functions violating $WPHPₙ^{2n}$ are one-way and, on the other hand, one-way permutations give rise to functions violating $PHPₙ^{n+1}$, and strongly collision-free families of hash functions give rise to functions violating $WPHPₙ^{2n}$ (all in suitable models of bounded arithmetic).
Further we formulate a few problems and conjectures; in particular, on the structured PHP (introduced here) and on the unrelativised WPHP.

LA - eng

KW - proof complexity; resolution; bounded arithmetic; weak pigeonhole principle; Ramsey theorem; lower bounds; one-way functions

UR - http://eudml.org/doc/282141

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.