Développement #595

Titre : Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet

Contenu : On montre les liens entre les problèmes de graphes et le calcul propositionnel.\rDans 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).\rDans l'autre sens, on part de CLIQUE dont on montre la NP-complétude à l'aide de SAT.

Créé le : 23/07/2026 12:42

Mis à jour : 23/07/2026 12:42