Partition

Problème de diviser un ensemble d’entiers en deux sous-ensembles de somme égale.

Problème de décision

• Instance : Séquence $S=⟨x_1,...,x_n⟩$ d’entiers
• Question : Existe-t-il deux sous-séquences $S_1$​ et $S_2$​ telles que :
  • $S_1\cup S_2=S$
  • $S_1\cap S_2=\varnothing$
  • ${\sum }_{x\in S_1}x={\sum }_{x\in S_2}x$

Complexité

Partition est NP-complet.

Certificat

• Certificat de verification : Indicateur pour chaque élément (dans $S_1$​ ou $S_2$​)
• Vérification : Calculer les sommes et vérifier l’égalité

Réductions

Partition ${\ll }_P$ Sous-somme

$f:⟨S⟩\to ⟨S,k=\frac{1}{2}\sum x⟩$

Sous-somme ${\ll }_P$​ Partition

$f:⟨S,k⟩\to ⟨S^{\prime }⟩$

où :

• $\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$

Idée : Les deux nouveaux éléments ne peuvent pas être dans la même partition.

Partition ${\ll }_P$​ Sac à dos (Knapsack)

$f:⟨S⟩\to ⟨O=S,w=u=S,B=k=\frac{1}{2}\sum x⟩$

Généralisations

3-Partition

Diviser en 3 sous-ensembles de somme égale (NP-complet).

Réduction depuis Partition :

$⟨S⟩\to ⟨S^{\prime }=S\cup \{\frac{k}{2}\}⟩$

où $k=\frac{1}{2}{\sum }_{x\in S}x$. Si $k$ est impair, retourner faux.

4-Partition

Similaire avec $S^{\prime }=S\cup \{\frac{k}{2},\frac{k}{2}\}$

Self-réductibilité

Partition est self-réductible.

Algorithme avec oracle

// partitiondec(S) -> oui/non   (oracle O(1))

// Idée : Déterminer si deux éléments seront dans la même partition

si !partitiondec(S):
	retourner faux
s1 = {x0}, s2 = {}
pour i = 2 à n:
	si partitiondec(S \ {xi}):
		s1 = s1 ∪ {xi}
	sinon:
		s2 = s2 ∪ {xi}
retourner (s1, s2)