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

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.