Développement : Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet

Détails/Enoncé :

On montre les liens entre les problèmes de graphes et le calcul propositionnel.
Dans un sens, on part de 2-SAT et on utilise un algorithme sur les graphes pour montrer que le problème est dans P (et même qu'il est NL-complet).
Dans l'autre sens, on part de CLIQUE dont on montre la NP-complétude à l'aide de SAT.

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 :

Computational complexity , Papadimitriou (utilisée dans 7 versions au total)
Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest (utilisée dans 49 versions au total)