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 2025 :

  • 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 75 versions au total)