CM6

IP (Integer programming) est NP-complet ? Certificat : un vecteur $z\in \{0,1{\}}^n$ Verification : $A\times z\le b$

3-partition NP-complet

Instance $S=<x_1,x_2,\dots ,x_n>$ une séquence d’entiers Question : il existe $S_1,S_2,S_3$ sous sequences de $S$ tel que $\cup S_i=S$ et ${\sum }_{x\in S_1}x={\sum }_{x\in S_2}x={\sum }_{x\in S_3}x$

NP ? Certificat : une permutation $P=1..|S|$ (les positions des entiers à prendre dans la séquence) Vérification : Polynomial (on construit du sous-ensemble à partir de la permutation)

NP-hard ? $<S>\to <S^{\prime }>$ $S^{\prime }=S\cup \frac{k}{2}$

k = $\frac{1}{2}{\sum }_{i\in S}x$ si k n’est pas pair retourner faux ajouter à S l’entier $\frac{k}{2}$ retourner 3P(S)

4-partition

Même chose avec $S^{\prime }=S\cup \{\frac{k}{2},\frac{k}{2}\}$

Dans l’examen : 3-partition ${\ll }_P$ partition

Balck box programming

Hypothèse que $P=NP$

$\ll$ : Réduction de Karp ${\ll }_{CT}$ : réduction de Cook-Turing

A decision problem $Q$ is Cook-Turing reducible to $Q^{\prime }$ if there is a polytime algo $A$ solving $Q$ whenever there is a poly-time algo $A^{\prime }$ solving $Q^{\prime }$.

A language $Q\in NP$ is self-reducible if there is a Cook-Turing reduction from the serach problem for $Q$ to the decision problem for $Q$.

Blackbox algo:

• input = instance d’un pb de recherche
• output = un algo poly pour le probleme de recherche

Exemple : CliqueMax L’oracle nous donne algocliquedec(G, k) → oui ou non (avec une complexité O(1)) On cherche un algo algoclique(G) qui retourne une clique de taille max.

TailleMax → algo poly

k = TailleMax(G) pour x $\in$ X : si algocliquedec(G|x): alors G = G|x retourner G

Donc cliquemax est self-reducible

Pareil pour HAM en retirant les arrètes

1. SAT est self-reducible
2. partition
3. SACADOS
4. Color
5. sous-graphe

SAT self-reducible

SATdec → oui/non Exemple: $\varphi =(x_1\vee \neg x_2\vee x_3)\wedge (\neg x_1\vee x_2)\wedge (x_2\vee \neg x_3)$ Idée : est-ce qu’il y a une solution avec $x_i=0$ Algo: si ! SATdec($C$): retourner faux v[] pour i = 1 a n: si SATdec($C_{x_i=0}$): $C$ = $C_{x_i=0}$ v[i] = 0 sinon: $C$ = $C_{x_i=1}$ v[i] = 1 retourner v

SACADOS self-reducible

sacadosdec(X, w, u, B, k) Idée : on cherche le k max. on fixe les variables $x_i\in X$ existe t il une solution avec $x=1$.

Algo: k = 1 tant que sacadosdec(X, w, u, B, k): k = k+1

Mais cet algo est exponentielle $O({\sum }_{x\in X}(u(x)))$ donc on peut utiliser la dichotomie

pour x $\in$ X: si sacadosdec(X, w, u, B, k): X = X \ (x) W = W \ (x) U = U \ (x) retourner X

Partition

partitiondec(S) → oui/non Idée : Est-ce que deux entiers seront ensemble dans la même partition ?

Exemple : <2, 3, 4, 3, 6, 7, 5> <5, 4, 3, 6, 7, 5> // Le 2 et 3 seront donc ensemble <9, 3, 6, 7, 5> <15, 3, 7, 5> <22, 3, 5>

s1 = <2, 3, 4, 6> s2 = <3, 7, 5>

Algo : si ! partitiondec(S): retourner faux s1 = {x0}, s2 = {} pour i = 2 a n: si partitiondec(S \ {xi}): s1 = s1 $\cup$ {xi} sinon: s2 = s2 $\cup$ {xi} retourner (s1, s2)

Color

colordec(G, k) → oui/non on a k min en O(n) Idée : Est-ce que deux sommets n’auront pas la même couleur ? Comment : on demande a l’oracle si on peut colorier le graphe avec une arete en plus entre les 2 sommets ?