Probabilistic Algorithms and Ramsey-Type Principles in Reverse Mathematics Laurent Bienvenu
Ludovic Patey
Paul Shafer
LIAFA
February 25, 2013
Bienvenu - Patey - Shafer (LIAFA)
Ramsey-Type K¨ onig’s Lemma
February 25, 2013
1 / 31
Summary
1
Introduction
2
Probabilistic Algorithms
3
Ramsey’s Theorems
4
Ramsey-Type Weak K¨ onig’s Lemmas
5
Conclusion
Bienvenu - Patey - Shafer (LIAFA)
Ramsey-Type K¨ onig’s Lemma
February 25, 2013
2 / 31
Plan
1
Introduction
2
Probabilistic Algorithms
3
Ramsey’s Theorems
4
Ramsey-Type Weak K¨ onig’s Lemmas
5
Conclusion
Bienvenu - Patey - Shafer (LIAFA)
Ramsey-Type K¨ onig’s Lemma
February 25, 2013
3 / 31
The ”big five” subsystems
Bienvenu - Patey - Shafer (LIAFA)
Ramsey-Type K¨ onig’s Lemma
February 25, 2013
4 / 31
The reverse mathematics zoo
Bienvenu - Patey - Shafer (LIAFA)
Ramsey-Type K¨ onig’s Lemma
February 25, 2013
5 / 31
Plan
1
Introduction
2
Probabilistic Algorithms
3
Ramsey’s Theorems
4
Ramsey-Type Weak K¨ onig’s Lemmas
5
Conclusion
Bienvenu - Patey - Shafer (LIAFA)
Ramsey-Type K¨ onig’s Lemma
February 25, 2013
6 / 31
Why probabilistic algorithms ?
Faster algorithms using randomness. Primality testing Cryptographic Sorting
Crucial questions in Complexity Theory BPP vs P
Which computational power ?
Bienvenu - Patey - Shafer (LIAFA)
Ramsey-Type K¨ onig’s Lemma
February 25, 2013
7 / 31
Weak Weak K¨onig’s Lemma
Definition (Tree) A tree T is a set closed under prefixes: ∀σ ∈ T , τ ≺ σ ⇒ τ ∈ T
Definition (Measure of a tree) def
µ(T ) = lim
n→∞
card {σ ∈ T : |σ| = n} 2n
Definition (WWKL0 ) RCA0 + Every subtree of 2
