¿Cómo puedo reducir el Subconjunto Suma a la Partición?

Question

Tal vez esto es bastante simple, pero tengo algunos problemas para conseguir esta reducción.Quiero reducir Subconjunto Suma a Partición pero en este momento no veo la relación!

Es posible reducir este problema a través de una Levin Reducción ?

Si usted no entiende escritura de aclaración!

Answer 1

Sea $ (l, b) $ una instancia de suma de subconjunto, donde $ L $ es una lista (multiset) de números, y $ B $ es la suma objetivo. Deje $ s = sum L $. Deje que $ L '$ sea la lista formada agregando $ S+B, 2S-B $ a $ L $.

(1) Si hay un sublista $ M Subseteq L $ sumando a $ B $, entonces $ L '$ puede dividirse en dos partes iguales: $ m cup {2s-b } $ y $ l setminus M CUP {S+B } $. De hecho, la primera parte suma a $ B+(2S-B) = 2s $, y la segunda a $ (SB)+(S+B) = 2S $.

(2) Si $ L '$ puede dividirse en dos partes iguales $ P_1, P_2 $, entonces hay un sublista de $ L $ suma a $ B $. De hecho, dado que $ (s+b)+(2s-b) = 3s $ y cada parte resume $ 2s $, los dos elementos pertenecen a diferentes partes. Sin pérdida de generalidad, $ 2SB en P_1 $. El resto de los elementos en $ P_1 $ pertenecen a $ L $ y suma a $ B $.

Answer 2

La respuesta mencionada por @Yuval Filmus es incorrecto (es correcto solo si no hay enteros negativos). Considere el siguiente Multiset:

$$\{-5, 2, 2, 2, 2, 2\} $$

y la suma objetivo es $ -2 $. Sabemos que no hay subconjunto. Ahora, construimos la instancia para el problema de la partición. Los dos elementos nuevos agregados son $ 2 Sigma-T = 12 $ y $ sigma+t = 3 $. El Multiset ahora es: $$ {-5, 2, 2, 2, 2, 2, 3, 12 } $$ y la suma total es de $ 20 $.

El problema de la partición resuelve la respuesta que da al subconjunto $$ {2, 2, 2, 2, 2 } $$ Aquí, los 2 elementos nuevos están en el mismo subconjunto (no hay otra forma de dividir en la mitad de la suma) . Por lo tanto, este es un mostrador. La respuesta correcta es la siguiente:

Agregue un elemento cuyo valor sea $ 2t- Sigma $. La suma total del Multiset ahora es de $ 2T $. Resuelva el problema de partición que dará 2 subconjuntos de suma $ t $. Solo una de las particiones contendrá el nuevo elemento. Elegimos la otra partición cuya suma es $ T $ y hemos resuelto el problema del subconjunto al reducirlo a un problema de partición. Esto es lo que el Enlace explica.

Answer 3

Aquí está una sencilla prueba:

Es fácil ver que la PARTICIÓN puede ser verificado en el polinomio de tiempo;dada una partición $P_1,P_2$ sólo la suma de las dos y verificar que sus sumas iguales el uno al otro, que es, obviamente, un polinomio de tiempo de verificación (porque la suma es un polinomio de operación y sólo estamos realizando en la mayoría de los $|X|$ muchos sumatorias).

El núcleo de la prueba está en la reducción de la SUBSETSUM a la PARTICIÓN;para ello conjunto dado $X$ y un valor $t$ (el subconjunto de la suma de la consulta) se forma un nuevo conjunto $X'=X \cup \{s-2t\}$ donde $s=\sum_{x \in X}x$.Para ver que esto es una reducción de:

• ($\implica$ ) suponga que existe alguna $S \subconjunto X$ tal que $t=\sum_{x \in S}x$ entonces tendríamos que \begin{ecuación*} s-t=\sum_{x \in S\cup \{ s-2t \} }x, \end{ecuación*} \begin{ecuación*} s-t=\sum_{x \in X' \setminus( S\cup \{s-2t\})}x \end{ecuación*} y tendríamos que $S\cup \{ s-2t \} $ y $X' \setminus( S\cup \{s-2t\})$ forma una partición de $X'$

• ($\impliedby $) Supongamos que hay una partición $P_1',P_2' $ de $X'$ tal que $\sum_{x \in P_1'}x= \sum_{x \in P_2'}x$.Aviso de que esta induce una partición física $P_1$ y $P_2$ de $X$ tal que WLOG tenemos que \begin{ecuación*} s-2t+\sum_{x \in P_1}x= \sum_{x \in P_2}x \end{ecuación*} \begin{ecuación*} \implica 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{ecuación*} \begin{ecuación*} \implica s-2t+2\sum_{x \in P_1}x = s \end{ecuación*} \begin{ecuación*} \implica \sum_{x \in P_1}x = t \end{ecuación*}

Por lo tanto, de una solución $t=\sum_{x \in S}x$ podemos formar una partición $P_1 =S\cup \{ s-2t \} $, $P_2=X' \setminus( S\cup \{s-2t\})$ y a la inversa a partir de una partición $P_1',P_2' $ podemos formar un soltuion $t=\sum_{x \in P_1'\setminus \{s-2t\}}x$ y por lo tanto la asignación de $f:(X,t) ightarrow X'$ es una reducción (porque $(X,t)$ es en el idioma/set SUBSETSUM $\Leftrightarrow X'=f(X,t)$ es en el idioma/PARTICIÓN del conjunto) y es claro ver que la transformación se realiza en el polinomio de tiempo.

Answer 4

Suma del subconjunto:

Entrada: {a1, a2, ..., am} st m = {1..m} y ai son enteros no negativos y s⊆ {1..k} y σai (i∈S) = t

Dividir:

Entrada: {a1, a2, ..., am} y s⊆ {1, · · ·, m} st σai (i∈S) = σaj (j∉s)

PRUEBA DE PARTICIÓN NP: Si Prover proporciona una partición (P1, P2) para el verificador, el verificador puede calcular fácilmente la suma de P1 y P2 y verificar si el resultado está 0 en tiempo lineal.

Np_hard: subsetsum ≤p partición

Sea x entrada de subsetsum y x = 〈a1, a2, ..., am, t〉 y σai (i de 1 a m) = a

Case1: 2t> = a:

Sea f (x) = 〈a1, a2, ..., am, am+1〉 donde am+1 = 2t -a

Queremos mostrar que x∈Subsetsum ⇔ f (x) ∈Partition

Entonces existen s⊆ {1, ..., m} st t = {1..m} - sy σai (i∈T) = AT

y deje t '= {1 ... m, m+1}-s so σaj (j∈T') = a-t+2t-a = t

que es exactamente σai (i∈S) = t y muestra f (x) ∈Partition

Ahora también mostraremos que f (x) ∈Partition ⇔ x∈Subsetsum

Entonces existen s⊆ {1, ..., m, m+1} st t = {1, ..., m, m+1} - sy σai (i∈T) = [a+(2t -a ) -t] = t

y muestra σai (i∈T) = σaj (j∈S) entonces m+1∈T y S⊆ {1, · · ·, m} y σai (i∈S) = t

Entonces x∈Subsetsum

Caso 2: 2t = <a :

Podemos verificar lo mismo, pero justo esta vez, AM+1 es A - 2T

Answer 5

Este enlace tiene una buena descripción de ambas reducciones, partición a subconjunto y suma de subconjunto a partición. Creo que es más obvio que YuvalRespuesta.enlace útil