Exercice 1 - 3-SAT/CLIQUE

3-SAT est défini de la façon suivante :

• Données : Un ensemble $\{C_j \vert j = 1, \ldots, p\}$ de clauses, un ensemble $\{x_i \vert i = 1, \ldots, n\}$ de variables. Chaque clause $C_j$ contient $3$ littéraux $\{l_j^1, l_j^2, l_j^3\}$ pouvant être de la forme $x_i$ ou $\neg x_i$, ce que l'on notera avec une égalité pour simplifier les notations.
• Question : Existe-t-il une valuation des variables satisfaisant au moins un littéral de chaque clause ?

Une clique est un sous-graphe complet. La taille d'une clique est le nombre de sommets qu'elle contient. On définit le problème CLIQUE de la façon suivante :

• Données : Une graphe $G$ non orienté, une constante $K>0$
• Question : Existe-t-il dans $G$ une clique de taille $K$ ?

Nous considérons la réduction suivante :

• $K = p$
• A chaque clause $C_i$, on associe trois sommets $s_j^1, s_j^2$ et $s_j^3$.
• Il existe une arête entre deux sommets $s_j^i$ et $s_{j^\prime}^{i^\prime}$ si
  • $j \not = j^\prime$
  • si $l_i^j = x$, alors $l_{j^\prime}^{i^\prime} \not = \neg x$

3-SAT est connu pour être NP-Complet, montrez que CLIQUE est NP-Complet.