Théorème de Cook
SAT est NP-complet.
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 913 | Machines de Turing. Applications.2021 |
| 5 | 915 | Classes de complexité. Exemples.2021 |
| 5 | 26 | Classes P et NP. Problèmes NP-complets. Exemples.2022 |
| 4 | 28 | Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.2022 |
Utilisateur : Devevey
Recasable dans la 916.
Références :
Langages formels, Calculabilité et Complexité - Carton
Utilisateur : Timothée
Références :