Développement #961
Titre : 2-SAT est NL-dur
Contenu : Ce développement présente différents résultats de complexité concernant le problème de satisfiabilité d’un fragment du calcul propositionnel. Les algorithmes présentés utilisent des procédures classiques sur les graphes orientés (calcul de composantes fortement connexes et tri topologique).
Créé le : 23/07/2026 12:42
Mis à jour : 23/07/2026 12:42
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 915 | Classes de complexité. Exemples.2021 |
| 4 | 925 | Graphes : représentations et algorithmes.2021 |
| 5 | 26 | Classes P et NP. Problèmes NP-complets. Exemples.2022 |
| 5 | 28 | Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.2022 |