Théorème de Cook
Théorème en informatique théorique / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Théorème de Cook?
Résumez cet article pour un enfant de 10 ans
En informatique théorique, plus précisément en théorie de la complexité, le théorème de Cook aussi appelé théorème de Cook-Levin est le théorème qui affirme que le problème SAT, c'est-à-dire le problème de satisfaisabilité d'une formule de la logique propositionnelle, est NP-complet. Il a été démontré en 1971 par Stephen Cook[1] et, sensiblement au même moment, par Leonid Levin[2].
Ce résultat est important car si on montre qu'il existe un algorithme en temps polynomial pour le problème SAT, alors le problème P = NP est résolu. Par ailleurs, ce résultat permet de montrer la NP-dureté de beaucoup d'autres problèmes, par réduction polynomiale.