Comment puis-je réduire la somme des sous-ensembles à la partition?

C'est peut-être assez simple, mais j'ai du mal à obtenir cette réduction. Je veux réduire la somme des sous-ensembles à la partition, mais pour le moment je ne vois pas la relation!

Est-il possible de réduire ce problème en utilisant une réduction Levin?

Si vous ne comprenez pas, écrivez pour obtenir des éclaircissements!

Soit une instance de somme de sous-ensemble, où est une liste (multiset) de nombres, et est la somme cible. Laissez . Soit soit la liste formée par l' addition à .$(L,B)$$L$$B$$S = \sum L$$L'$$S+B,2S-B$$L$

(1) S'il existe une sous-liste sommant à , alors peut être partitionné en deux parties égales: et . En effet, la première partie résume à , et la seconde à .$M \subseteq L$$B$$L'$$M \cup \{ 2S-B \}$$L\setminus M \cup \{ S+B \}$$B+(2S-B) = 2S$$(S-B)+(S+B) = 2S$

(2) peut être divisé en deux parties égales , alors il existe une sous - liste de sommation de . En effet, puisque et chaque partie résume à , les deux éléments appartiennent à des parties différentes. Sans perte de généralité, . Le reste des éléments dans appartiennent à et la somme de .P 1 , P 2 L B ( S + B ) + ( 2 S - B ) = 3 S 2 S 2 S - B ∈ P 1 P 1 L $L'$$P_1,P_2$$L$$B$$(S+B)+(2S-B) = 3S$$2S$$2S-B \in P_1$$P_1$$L$$B$

La réponse mentionnée par @Yuval Filmus est incorrecte (elle est correcte UNIQUEMENT s'il n'y a pas d'entiers négatifs). Considérez le multiset suivant:

et la somme cible est . Nous savons qu'il n'y a pas de sous-ensemble. Maintenant, nous construisons l'instance pour le problème de partition. Les deux nouveaux éléments ajoutés sont et . Le multiset est maintenant: et la somme totale est de .2 σ - t = 12 σ + t = 3 { - 5 , 2 , 2 , 2 , 2 , 2 , 3 , 12 } $-2$$2\sigma-t = 12$$\sigma+t = 3$

Le problème de partition résout la réponse en donnant le sous-ensemble Ici, les 2 nouveaux éléments sont dans le même sous-ensemble (il n'y a pas d'autre moyen de partitionner la moitié de la somme). Par conséquent, ceci est un contre-exemple. La bonne réponse est la suivante:

Ajoutez un élément dont la valeur est . La somme totale du multiset est maintenant de . Résoudre le problème de partition qui donnera 2 sous-ensembles de somme . Une seule de la partition contiendra le nouvel élément. Nous choisissons l'autre partition dont la somme est et nous avons résolu le problème de sous-ensemble en le réduisant en un problème de partition. C'est ce que le lien explique.2 t t $2t-\sigma$$2t$$t$$t$

Voici une preuve simple:

Il est facile de voir que SET-PARTITION peut être vérifié en temps polynomial; étant donné une partition $P_1,P_2$ additionne simplement les deux et vérifie que leurs sommes sont égales, ce qui est évidemment une vérification temporelle polynomiale (car la sommation est une opération polynomiale et nous effectuons seulement $|X|$ plusieurs sommations au maximum).

$X$$t$$X'=X \cup \{s-2t\}$$s=\sum_{x \in X}x$

• ($\implies$$S \subset X$$t=\sum_{x \in S}x$

  $$\begin{equation*} s-t=\sum_{x \in S\cup \{ s-2t \} }x, \end{equation*}$$ $$\begin{equation*} s-t=\sum_{x \in X' \setminus( S\cup \{s-2t\})}x \end{equation*}$$ $S\cup \{ s-2t \}$$X' \setminus( S\cup \{s-2t\})$$X'$

• ($\impliedby$$P_1',P_2'$$X'$$\sum_{x \in P_1'}x= \sum_{x \in P_2'}x$$P_1$$P_2$$X$

  $$\begin{equation*} s-2t+\sum_{x \in P_1}x= \sum_{x \in P_2}x \end{equation*}$$ $$\begin{equation*} \implies s-2t+\sum_{x \in P_1}x+\sum_{x \in P_1}x= \sum_{x \in P_2}x+\sum_{x \in P_1}x = s \end{equation*}$$ $$\begin{equation*} \implies s-2t+2\sum_{x \in P_1}x = s \end{equation*}$$ $$\begin{equation*} \implies \sum_{x \in P_1}x = t \end{equation*}$$

$t=\sum_{x \in S}x$$P_1 =S\cup \{ s-2t \}$$P_2=X' \setminus( S\cup \{s-2t\})$$P_1',P_2'$$t=\sum_{x \in P_1'\setminus \{s-2t\}}x$$f:(X,t)\rightarrow X'$$(X,t)$$\Leftrightarrow X'=f(X,t)$

Somme de sous-ensemble:

Entrée: {a1, a2, ..., am} st M = {1..m} et ai sont des nombres entiers non négatifs et S⊆ {1..k} et Σai (i∈S) = t

Cloison:

Entrée: {a1, a2, ..., am} et S⊆ {1, · · ·, m} st Σai (i∈S) = Σaj (j∉S)

Partition Np Proof: si le prouveur fournit des partitions (P1, P2) pour le vérificateur, le vérificateur peut facilement calculer la somme de P1 et P2 et vérifier si le résultat est 0 en temps linéaire.

NP_Hard: SubsetSum ≤p PARTITION

Soit x l'entrée de SubsetSum et x = 〈a1, a2, ..., am, t〉 et Σai (i de 1 à m) = a

Cas 1: 2t> = a:

Soit f (x) = 〈a1, a2, ..., am, am + 1〉 où am + 1 = 2t − a

Nous voulons montrer que x∈SubsetSum ⇔ f (x) ∈PARTITION

donc il existe S⊆ {1, ..., m} st T = {1..m} - S et Σai (i∈T) = at

et Soit T '= {1 ... m, m + 1} - S donc Σaj (j∈T') = a-t + 2t-a = t

qui est exactement Σai (i∈S) = t et il montre f (x) ∈PARTITION

maintenant, nous allons également montrer que f (x) ∈PARTITION ⇔ x∈SubsetSum

il existe donc S⊆ {1, ..., m, m + 1} st T = {1, ..., m, m + 1} - S et Σai (i∈T) = [a + (2t-a ) -t] = t

et il montre Σai (i∈T) = Σaj (j∈S) donc m + 1∈T et S⊆ {1, · · ·, m} et Σai (i∈S) = t

donc x∈SubsetSum

Cas 2: 2t = <a :

nous pouvons vérifier la même chose, mais cette fois-ci, am + 1 est a − 2t

ce lien a une bonne description des deux réductions, partition à sous-ensemble-somme et sous-ensemble-somme à partitionner. Je pense que c'est plus évident que la réponse de YUVAL . lien utile