Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 7 Juin 2011

Quelle puissance ont les algorithmes probabilistes polynomiaux ?

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr