Laurent Bienvenu, Montpelier, CNRS
"Randomized algorithms in computability theory"
Are randomized algorithms more powerful than deterministic ones? This is perhaps one of the most important general questions in computational complexity, the problem P ?= BPP perhaps being the best known instance of it. In computability theory, this question is typically less considered because of a theorem of De Leeuw et al., which states that if a given sequence/language can be probabilistically computed, it can in fact be deterministically computed. However the problem remains interesting if one consider classes of objects: there are some classes C containing no computable element but for which there is a probabilistic algorithm which produces an element of C with positive probability. We will discuss some some positive and negative examples and will explain how to get a quantitative analysis of such classes using Kolmogorov complexity, with numerous applications to algorithmic randomness. Finally, we will see how the theorem of De Leeuw et al. can be turned around to get the existence of computable objects from probabilistic algorithms.
MC 5501