Épisode 2 de la série « Henri Potier à l’école de la complexité ».

Quand on conçoit un algorithme, une question est : « est-ce qu’il fait bien le boulot ? » Une autre est : « combien de temps il va prendre ?» Si ça met deux plombes pour me dire où trouver une pizza, ça m’intéresse moins. Le domaine qui traite du temps que va prendre un algorithme (ou de la quantité de mémoire dont il va avoir besoin) s’appelle « la complexité algorithmique ». Un premier article de la série « Henri Potier à l’école de la complexité » avait expliqué comment compter le temps de calcul d’un algorithme. Dans ce deuxième article, nous allons explorer des problèmes importants pour lesquels aucun algorithme efficace n’est connu, et on ignore même s’il en existe.

Lire l'article de Sylvain Perifel et Guillaume Lagarde sur Binaire