PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Fundamenta Mathematicae

2001 | 170 | 1-2 | 123-140
Tytuł artykułu

### On the weak pigeonhole principle

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Kategorie tematyczne
Czasopismo
Rocznik
Tom
Numer
Strony
123-140
Opis fizyczny
Daty
wydano
2001
Twórcy
autor
• Mathematical Institute, Academy of Sciences, Žitná 25, CZ-115 67 Praha 1, The Czech Republic
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory