Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On the weak pigeonhole principle

100%

Krajíček J.

Fundamenta Mathematicae

2001

tom 170

nr 1-2

123-140

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.

Diagonalization in proof complexity

100%

Krajíček J.

Fundamenta Mathematicae

2004

tom 182

nr 2

181-192

We study diagonalization in the context of implicit proofs of [10]. We prove that at least one of the following three conjectures is true: ∙ There is a function f: {0,1}* → {0,1} computable in 𝓔 that has circuit complexity $2^{Ω(n)}$. ∙ 𝓝 𝓟 ≠ co 𝓝 𝓟. ∙ There is no p-optimal propositional proof system. We note that a variant of the statement (either 𝓝 𝓟 ≠ co 𝓝 𝓟 or 𝓝 𝓔 ∩ co 𝓝 𝓔 contains a function $2^{Ω(n)}$ hard on average) seems to have a bearing on the existence of good proof complexity generators. In particular, we prove that if a minor variant of a recent conjecture of Razborov [17, Conjecture 2] is true (stating conditional lower bounds for the Extended Frege proof system EF) then actually unconditional lower bounds would follow for EF.

Ograniczanie wyników

2 Fundamenta Mathematicae

2 Krajíček J.

1 2004

1 2001

Wyniki wyszukiwania

On the weak pigeonhole principle

Diagonalization in proof complexity