Exercice 6 - PARTITION/SUBSET SUM

Le problème PARTITION est défini comme suit :

• Données : un ensemble $A = \{p_i \vert i \in \{1, \ldots, n\}\}$ de $n$ valeurs, tel que
  
  $$\Sigma_{i = 1}^np_i$$
  
  
  est pair.
• Question : existe-t-il un sous-ensemble $I$ de $\{1, \ldots, n\}$ tel que
  
  $$\Sigma_{i \in I}p_i = \Sigma_{i \not \in I}p_i$$
  
  

Montrez que SUBSET SUM est NP-Complet, utilisez le fait que PARTITION est NP-Complet.