Reducción de la suma subconjunto a la partición

Question

Suma subconjunto: Dada una lista de números, encuentre si un sublista no vacío tiene Sum 0 (hay una variación donde queremos Sum = K en lugar de 0, pero 0 es más fácil para el análisis)

Dividir: Dada una lista, ¿se puede dividir en dos sublistas no vacíos con la misma suma?

Quiero reducir el suma de subconjunto a la partición. Las reducciones que encontré hasta ahora son las mismas que Éste Pero tiene las siguientes fallas:

1. Por $ b = 0 $, siempre puede dividir $ l '$ en $ {2s-0 } $, $ {s+0 } ul $.
2. ¡Supongamos que $ 2SB $ y $ S+B $ tienen que ir a diferentes particiones! Podrían tener a ambos en la misma partición junto con elementos que suman $ -s $, por lo tanto, suma total $ = 2s $ según sea necesario.

Answer 1

1. Tienes toda la razón que esta partición siempre ocurre. Si considera lo que esto significa en términos del subconjunto correspondiente, encontrará que esto indica que el conjunto vacío (que siempre es un subconjunto) tiene suma 0. De hecho, esto indica que siempre hay una solución para el subconjunto cuando el subconjunto cuando El objetivo es 0, que es exactamente como se esperaba. Resulta que arreglar la suma objetivo a 0 no solo hace que el problema sea más fácil de discutir, sino que hace que sea más fácil en un sentido de complejidad ($ o (1) $ al generar sí inmediatamente).

2. También estás aquí. Hay una formulación de suma de subconjunto donde la entrada es una lista de enteros positivos, y creo que la reducción que está leyendo fue de ese idioma. El objetivo era que nuestros elementos adicionales sean lo suficientemente grandes como para que ambos no puedan ir en la misma parte. Para reparar eso, podemos usar la suma de los valores absolutos. En realidad, esto muestra mejor parte de la estructura de la prueba, porque $ 2s $ fue en realidad $ S +$ ADEMPLE-LARGE-AUTH-NUMBER-para, que- $ S $ -Will-Suffice-but-So-Do-Larger- números.

En este punto, estoy copiando de la publicación vinculada y solo edito para manejar los negativos:

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 $ y elija $ s '> sum_ {l in l} | l | $. Deje que $ L '$ sea la lista formada agregando $ S'+B, S '+SB $ a $ L $.

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

(2) Si $ L '$ puede dividirse en dos partes iguales $ P_1, P_2 $, entonces hay un sublista de $ L $ suma a $ B $. La suma de los dos elementos nuevos es $ (S '+B)+(S'+Sb) = 2s '+S $. Todos los subconjuntos $ a subset l $ tienen $ izquierda | sum a right | <S '$, por lo que no es posible que $ {S'+Sb } cup {s '+b } cup a $ tenga suma $ s'+s $ (siempre es mayor). Entonces los dos elementos nuevos pertenecen a diferentes partes. Sin pérdida de generalidad, $ S '+SB en P_1 $. El resto de los elementos en $ P_1 $ pertenecen a $ L $ y suma a $ B $; No incluyen un nuevo elemento, por lo que son una solución a la suma del subconjunto.