Calculabilité - Exercices

Exercice

Soit \(G = (S,A)\) un graphe non orienté.

On dit que \(X \subset S\) est :

  • une clique lorsque \(\forall x, y \in X, x \neq y \Rightarrow \{ x, y\} \in A\)
  • un ensemble indépendant lorsque \(\forall x, y \in X, \{ x, y\} \not\in A\)
  • une couverture de sommets lorsque \(\forall \{x, y\} \in A, x \in X \vee y \in X\)

On note ici \(\overline{G} = (S, \overline{A})\) où \(\forall x, y \in S, x \neq y \Rightarrow (\{ x, y\} \in \overline{A} \iff \{x, y\} \not\in A)\).

On s'intéresse aux problèmes suivants :

Problème MaxClique

  • Entrée : un graphe non orienté \(G = (S,A)\) et un entier \(k\).
  • Sortie : existe-t-il une clique de \(G\) de cardinal \(\ge k\) ?

Problème MaxIndSet

  • Entrée : un graphe non orienté \(G = (S,A)\) et un entier \(k\).
  • Sortie : existe-t-il un ensemble indépendant de \(G\) de cardinal \(\ge k\) ?

Problème MinVertexCover

  • Entrée : un graphe non orienté \(G = (S,A)\) et un entier \(k\).
  • Sortie : existe-t-il une couverture de sommets de \(G\) de cardinal \(\le k\) ?

Questions :

  1. Montrer que MaxIndSet est NP-complet par réduction de 3-SAT.
  2. Soit \(X \subset S\), montrer que les propriétés suivantes sont équivalentes :
    • (a) \(X\) est un ensemble indépendant de \(G\) ;
    • (b) \(X\) est une clique de \(\overline{G}\) ;
    • (c) \(S \setminus X\) est une couverture de sommets de \(G\).
  3. En déduire que MinVertexCover et MaxClique sont NP-complets.

Exercice

On vient de voir des problèmes de décision avec seuil. Ce sont des problèmes de décision classiques qu'on peut déduire de problèmes d'optimisation comme :

Problème MaxCliqueOpt

  • Entrée : un graphe non orienté \(G = (S,A)\).
  • Sortie : quel est le cardinal maximal d'une clique de \(G\) ?

Montrer que si MaxClique est dans P alors MaxCliqueOpt peut également être résolu en temps polynomial.

Exercice

Problème SubsetSum

  • Entrée : un multiensemble fini \(X\) d'éléments de \(\N^*\) et \(T \in \N\).
  • Sortie : existe-t-il un sous-multiensemble \(V \subset X\) tel que \(\sum_{x \in V} x = T\) ?

Questions :

  1. Montrer que SubsetSum est dans NP.
  2. On va montrer que SubsetSum est NP-complet par réduction de MinVertexCover. Soit \((G, k)\) une instance de MinVertexCover avec \(G = (S,A)\) et \(k \le |S|\) (sinon l'instance est trivialement positive). On considère une numérotation dans \(\range{0}{|A|-1}\) des arêtes et on pose pour la \(i\)-ème arête \(b_i = 4^i\). Pour chaque sommet \(x \in S\), on pose \(a_x = 4^{|A|} + \sum_{i \text{ incidente à } x} 4^i\). On pose également \(T = k 4^{|A|} + \sum_{i = 0}^{|A|-1} 2 \cdot 4^i\) et on note \(X\) le multiensemble formé des \(b_0, \dots, b_{|A|-1}\) et des \(a_x\) pour \(x \in S\). Montrer qu'on a bien une réduction polynomiale permettant de prouver que SubsetSum est NP-difficile, et donc NP-complet.
  3. Résoudre SubsetSum par programmation dynamique. On obtient alors un algorithme en \(O(|X| T)\). A-t-on prouvé P=NP ?

Exercice

On considère le problème BoxDepth qui étant donnés \(n\) rectangles dont les côtés sont parallèles aux axes d'un repère orthonormé, détermine le plus grand sous-ensemble de rectangles ayant un point en commun.

  1. Décrire une réduction polynomiale de BoxDepth vers MaxClique.
  2. Montrer que BoxDepth est dans P.
  3. Pourquoi n'a-t-on pas résolu P=NP ?

Exercice

On considère DNF-SAT qui est le pendant de CNF-SAT avec une formule en entrée donnée sous forme normale disjonctive.

  1. Montrer que DNF-SAT est dans P.
  2. Pourquoi ne peut-on pas en déduire que 3-SAT est dans P en mettant la formule sous forme normale disjonctive ?

Exercice

Le problème 3-SAT-AllOrNothing cherche à déterminer s'il existe une valuation d'une formule de 3-SAT dans laquelle chaque clause contient soit trois littéraux vrais, soit trois littéraux faux.

  1. Montrer que ce problème est dans P.
  2. Pourquoi n'a-t-on pas résolu P=NP ?

Exercice

Le problème Partition consiste, étant donné un multiensemble \(S\) de \(n\) entiers naturels, à déterminer s'il existe deux sous-multiensembles \(A,B \subset S\) tels que \(A\cup B = S, A \cap B = \emptyset\) et

\[ \sum_{a \in A} a = \sum_{b \in B} b \]
  1. Montrer que Partition est NP-complet.
  2. Donner un algorithme en temps \(O(nM)\) où \(M = \sum_{s \in S} s\) résolvant Partition.
  3. A-t-on démontré que P=NP ?
  4. On s'intéresse maintenant au problème 2-Partition : étant donnés \(2n\) entiers, peut-on les séparer en \(n\) paires de même somme ? Montrer que 2-Partition est dans P.