T
Rare
Théorème de Cook
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 et, sensiblement au même moment, par L…
Extrait raccourci de l'article Wikipédia, CC BY-SA 4.0.