CM5

Problème : SAT, 3-SAT, MIS $\in$ NP-Complet Question : Montrer que VC $\in$ NP-complet

• VC $\in$ NP
• $MIS{\ll }_{P}VC$ On sait que $VC$ est NP difficile car $MIS{\ll }_{P}VC$ $VC\in NP$

HAM Input : $G=(V,E)$ Question : $G$ est il Hamiltonien

• $HAM\in NP$ Certificat : P une permutation de V Verification : Pour i = 2 à n : si P[i-1] P[i] $\notin$ E alors retourner faux retourner vrai

  Donc O(n) Théorème : HAM est NP-complet Même question pour HC (Cycle hamiltonien)

On cherche à prouver que $HAM{\ll }_{P}HC$ $f:I(HAM)\to I(HC)$ $<G=(V,E)>$ $<G^{\prime }=(V^{\prime },E^{\prime })>$ $G^{\prime }$ est le graphe $G$ avec un sommet universel $z$ en plus qui est connecté à tous les sommets.

$G\in L(HAM)⟹G^{\prime }\in L(HC)$ et $G^{\prime }\in L(HC)⟹G\in L(HAM)$

L’arbre couvrant avec le minimum de feuilles est NP-hard $HAM{\ll }_{P}MLST$ $<G=(V,E)>\to <G^{\prime }=(V^{\prime },E^{\prime }),k>$ $G^{\prime }=G$ $k=2$ Donc si pour $k=2$, le problème est difficile, donc on a prouvé que MLST est difficile. HAM est un cas particulier de MLST.

Partition

Instance : $S=<x_1,\dots ,x_n$ une séquence de $n$ entiers Question : Existe-t-il deux sous séquence $S_1$ et $S_2$ tel que ${\sum }_{x\in S_1}x={\sum }_{x\in S_2}x$ et $S_1\cup S_2=S$

Sous-somme

Instance : $S=<x_1,\dots ,x_n$ une séquence de $n$ entiers

Questions

1. Partition ${\ll }_P$ Sous-somme $f:I(Partition)\to I(\text{Sous-somme})$ $<s>\to <s,\frac{1}{2}\sum x>$
2. Sous-somme ${\ll }_P$ Partition $<s,k>\to <s>$ $\sigma ={\sum }_{x\in S}x$ $S^{\prime }=S\cup \{x_{n+1},x_{n+2}\}$ $x_{n+1}=\sigma +k$ $x_{n+2}=2\sigma -k$ Les 2 nouveaux x ne peuvent pas etre dans la meme partition
3. Partition ${\ll }_P$ Sac à dos $f:I(\text{partition})\to I(\text{sac-a-dos})$ $<S>\to <O,w,u,B,k>$ $O=S$ $B=k=\frac{1}{2}\sum x$ $w=u=$
4. Sac à dos ${\ll }_P$ Partition On sait que: - $\sum w(O_i)\le \frac{1}{2}\sum x$ - $\sum u(O_i)\ge \frac{1}{2}\sum x$ - $w(O_i)=u(O_i)=x_i$
5. Sous-somme ${\ll }_P$ Sac à dos En utilisant la transitivité (Merci Benji) Sous-somme ${\ll }_P$ Partition ${\ll }_P$ Sac à dos En utilisant pas la transitivité $<S,k>\to <S,S,>$

Exercice à faire pour la semaine prochaine

Démontrer 3-Partition et 4-Partition NP-Complet Bin-Packing NP-complet