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.

Références utilisées dans les versions de ce développement :

131 Développements pour l’oral, D. Lesesvre, P. Montagnon, P. Le Barbenchon, T. Pierron (utilisée dans 56 versions au total)