Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet
On montre les liens entre les problèmes de graphes et le calcul propositionnel.\rDans un sens, on part de 2-SAT et on utilise un algorithme sur les graphes pour montrer que le problème est dans P (et même qu'il est NL-complet).\rDans l'autre sens, on part de CLIQUE dont on montre la NP-complétude à l'aide de SAT.
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 915 | Classes de complexité. Exemples.2021 |
| 5 | 28 | Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.2022 |
| 4 | 925 | Graphes : représentations et algorithmes.2021 |
| 4 | 26 | Classes P et NP. Problèmes NP-complets. Exemples.2022 |
Utilisateur : Devevey
Références :
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Computational complexity - Papadimitriou
Utilisateur : sieghttct
Papadimitriou pour 2-SAT, Cormen pour CLIQUE.
Références :
Computational complexity - Papadimitriou
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest