Développement : 2-SAT est NL-dur

Détails/Enoncé :

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).

Autres années :