L'intrigante question P = NP ?
Publié le dimanche 27 août 2017 20:00 - Mis à jour le dimanche 27 août 2017 20:00
Ce texte (voir la ressource ci-dessous) présente ce qu'est un problème de décision (réponse oui/non) et ce qu'est la longueur d'un algorithme en fonction de la taille des données d'entrée. Il définit ensuite la classe P des problèmes résolubles en « temps polynomial » (en fonction de la taille des données) et la classe NP des problèmes « vérifiables » en « temps polynomial » (une solution fournie peut être vérifiée ainsi) quand la réponse est oui.
P est inclus dans NP mais la réciproque est une célèbre conjecture. Ces points sont (quelque peu) formalisés dans une annexe Internet comportant une bibliographie.Une version allégée de ce texte figure à la page "Terminale".
Pièces jointes
À télécharger
Commentaires
Aucun commentaire