2-SAT est NL-dur
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).
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 915 | Classes de complexité. Exemples.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 |
| 4 | 925 | Graphes : représentations et algorithmes.2021 |
Utilisateur : Volgaar
Références :
131 Développements pour l’oral - D. Lesesvre, P. Montagnon, P. Le Barbenchon, T. Pierron