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

  • Pas de recasages pour cette année.