La recherche exhaustive
(ou comment trouver une aiguille dans une botte de foin ?)

Gilles Dowek

Dans cette conférence, on présente un certain nombre de problèmes qui peuvent être résolus par une méthode de recherche exhaustive: les équations diophantiennes, le jeu du solitaire, le problème des quatre couleurs, la recherche de démonstrations, le remplissage d'un sac, ... Tout au long de ce parcours, les mêmes questions reviennent sans cesse: dans quels cas peut-on limiter la recherche à un domaine fini, et dans quels cas cela est-il impossible ? Dans quels cas, peut-on effectuer une quantité raisonnable de calculs et dans quels cas cela est-il impossible ? Ces questions ont amené des développements mathématiques nouveaux au cours du XXème siècle. Les méthodes exhaustives ont donc permis de résoudre certains problèmes mathématiques, mais elles ont surtout permis d'en poser de nouveaux... dont certains ne sont toujours pas résolus.