CM4

Rappel

Algo non-déterministe :

• Certificat de taille poly
• Vérification en temps poly Exemple : MIS, CliqueMax, etc…

Transformation poly (${\ll }_P$)

Soient $Q_1,Q_2\in NP$ $f:I(Q_1)\to I(Q_2)$ f est calculable en temps poly $i\in L(Q_1)ssif(i)\in L(Q_2)$ Propriétés :

1. on suppose $Q_1{\ll }_p{Q}_2$ on a $Q_2\in P⟹Q_1\in P$
2. $Q_1\notin P⟹Q_2\notin P$
3. ${\ll }_{P}esttransitive$ $Q_1{\ll }_P$ et $Q_2{\ll }_P{Q}_3⟹Q_1{\ll }_P{Q}_3$

Exemple : $\text{Clique}{\ll }_{P}MIS{\ll }_{P}VC$ $f:<G,k>\to <\bar{G},k>$ $g:<G,k>\to <G,n-k>$ $g\circ f:<G,k>\to <\bar{G},n-k>$

Difficulté des problèmes

Sous classe de NP des problèmes les plus difficiles

Définition : Soit $Q$ un problème de décision. $Q$ est dit NP-difficile (NP-hard) si $\forall Q^{\prime }\in NP$ $Q^{\prime }{\ll }_{P}Q$ Cette definition n’est pas appliquable car il faut tous les pb de NP connus ou non.

Exemple d’un problème NP-hard qui n’est pas dans NP : Arrêt d’une machine de Turing (indécidable)

Définition : $Q$ est dit NP-complet si $Q$ est NP-difficile et $Q\in NP$

Indication : On suppose que

• $Q\in$ NP-complet
• $Q{\ll }_P{Q}^{\prime }$ Que peut-on dire que $Q^{\prime }$ ?

Théorème : Si $Q\in$ NP-complet et $Q{\ll }_P{Q}^{\prime }$ $Q^{\prime }$, alors $Q^{\prime }$ est un problème NP-hard.

Preuve : À prouver : $\forall Q^{\prime \prime }\in NP$ $Q^{\prime \prime }{\ll }_P{Q}^{\prime }$ Soit $Q^{\prime \prime }\in NP⟹Q^{\prime \prime }{\ll }_{P}Q$ On a aussi $Q{\ll }_P{Q}^{\prime }$ Par transitivité $Q^{\prime \prime }{\ll }_P{Q}^{\prime }$

Pour démontrer qu’un problème $Q$ est NP-difficile, il suffit de choisir le problème $Q^{\prime }$ NP-complet et faire la réduction de $Q^{\prime }{\ll }_{P}Q$.

Théorème : Cook 1972 SAT est NP-complet

3-SAT et SAT sont dans NP Preuve :

• Certificat : $V\in {0,1}^n$
• Verification : Si $\forall i\in [1,n]$ $V(C_i)=1$ alors retourner oui $O(n\times m)$

Théorème : 3-SAT est NP-complet Preuve :

• le 3-SAT $\in$ NP $SAT{\ll }_{P}3SAT$ $f:I(SAT)\to I(3SAT)$ soit C une instance de SAT

1. $k=1$ $C=(l_1)$ on ajoute 2 variables $y_1$ et $y_2$ et on remplace C par $\{(l_1\vee y_1\vee y_2),(l_1\vee \overline{y_1}\vee \overline{y_2}),(l_1\vee y_1\vee \overline{y_2}),(l_1\vee \overline{y_1})\vee y_2)\}$ Supposons que C est satisfiable ⇒ $l_1=1$ ⇒ les 4 clauses sont satisfiable. Supposons que les 4 clauses sont satisfiable

$y_1$	$y_2$	$l_1$
0	0	$l_1=1$
0	1	$l_1=1$
1	0	$l_1=1$
1	1	$l_1=1$

2. $k=2$ $C=(l_1,l_2)$ On rajoute une variable $y$ et on remplace C par $\{(l_1\vee l_2\vee y),(l_1\vee l_2\vee \bar{y})\}$

$y$	$l_1$
0	$l_1=1$
1	$l_1=1$

3. $k=3$ Rien à faire

4. $k\ge 4$ Preuve à faire

Théorème : 2-SAT $\in$ P On suppose que toutes les clauses ont exactement 2 littéraux Preuve : $(x,y),(\bar{x},y),(x,\bar{y}),(\bar{x},\bar{y})$

Théorème : MIS $\in$ NP-complet Preuve :

• MIS $\in$ NP
• 3-SAT ${\ll }_P$ MIS $f:I(3SAT)\to I(MIS)$ Exemple $C=(x_1\vee \overline{x_2}\vee x_3),(\overline{x_1}\vee x_2\vee \overline{x_3}),(x_1\vee x_2\vee x_3)$

$C$ est satisfiable ssi G a un stable de taille m.