On the weak pigeonhole principle

Jan Krajíček¹

¹ Mathematical Institute Academy of Sciences Žitná 25 CZ-115 67 Praha 1, The Czech Republic

Fundamenta Mathematicae, Tome 170 (2001) no. 1, pp. 123-140.

Résumé

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 $\mathop {{\rm WPHP}^{2n}_n}$ are one-way and, on the other hand, one-way permutations give rise to functions violating $\mathop {{\rm PHP}^{n+1}_n}$, and strongly collision-free families of hash functions give rise to functions violating $\mathop {{\rm WPHP}^{2n}_n}$ (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.

Détail

DOI : 10.4064/fm170-1-8

Keywords: investigate proof complexity extensions resolution bounded arithmetic weak pigeonhole principle ramsey theorem particular link proof complexities these principles further lower bounds width resolution proofs size extensions tree like resolution proofs ramsey theorem establish connection between provability wphp fragments bounded arithmetic cryptographic assumptions existence one way functions particular functions violating mathop wphp one way other one way permutations rise functions violating mathop php strongly collision free families hash functions rise functions violating mathop wphp suitable models bounded arithmetic further formulate few problems conjectures particular structured php introduced here unrelativised wphp