Sylvain Perifel (LIAFA, Paris 7)

Peut-on résoudre plus de choses en temps polynomial si nos algorithmes sont autorisés à tirer à pile ou face ? Plus modestement, grâce à l’aléatoire, peut-on résoudre en temps polynomial tous les problèmes exponentiels ? Nous nous intéresserons à cette dernière question (“EXP = BPP ?”), dont la réponse est dans doute “non” mais qui reste ouverte depuis longtemps… Nous insisterons sur les motivations, les progrès et les difficultés, avant de donner quelques pistes à explorer.