| dbo:abstract
|
- 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 et, sensiblement au même moment, par Leonid Levin. 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. (fr)
- 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 et, sensiblement au même moment, par Leonid Levin. 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. (fr)
|
| rdfs:comment
|
- 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 et, sensiblement au même moment, par Leonid Levin. (fr)
- 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 et, sensiblement au même moment, par Leonid Levin. (fr)
|
