La partición establecida es NP completa

Establecer problema de partición : el problema de partición de conjunto divide una array de números en dos subconjuntos de modo que la suma de cada uno de estos dos subconjuntos sea la misma. Sea S un conjunto de números y A un subconjunto de números con suma S1 , entonces existe otro subconjunto que contiene el resto de los elementos (S – A) con suma S2 , y S1 es igual a S2 .  

Planteamiento del problema : dado un conjunto S de N números, la tarea es determinar si el conjunto contiene dos particiones de S , y ambas tienen exactamente la misma suma.  

Explicación :
una instancia del problema es una entrada especificada para el problema. Una instancia del problema de la partición de conjuntos es un conjunto S , y la tarea es verificar si existen dos particiones de S que no se superpongan y que tengan una suma de elementos como sum . Dado que un problema NP-Completo es un problema que está tanto en NP como en NP-difícil , la prueba de la afirmación de que un problema es NP-Completo consta de dos partes:

1. El problema en sí está en la clase NP.
2. Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso. (B es reducible en tiempo polinomial a C se denota como B ≤ P ^C )

Si solo se cumple la segunda condición , el problema se llama NP-Hard .

Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Por lo tanto, para mostrar que un problema es NP-Completo, pruebe que el problema está en NP y cualquier problema NP-Completo es reducible a eso, es decir, si B es NP-Completo y B ≤ P ^C Para C en NP, entonces C es NP -Completo. Por lo tanto, se puede concluir que el problema de la partición de Conjuntos es NP-Completo utilizando las siguientes dos proposiciones:

El problema de la partición del conjunto está en NP:
si algún problema está en NP, entonces, dado un ‘certificado’, que es una solución al problema y una instancia del problema (un conjunto S y dos particiones A y A’ , en este caso ), se puede demostrar que el certificado en tiempo polinomial. Esto se puede hacer de la siguiente manera:  

1. Para cada elemento x en A y x’ en A’ , verifique que todos los elementos pertenecientes a S estén cubiertos.
2. Sea S1 es 0, S2 es 0
3. Para cada elemento x en A , agregue ese valor a S1 .
4. Para cada elemento x’ en A’ agregue ese valor a S2 .
5. Verifique que S1 sea lo mismo que S2 .

El algoritmo toma tiempo lineal en el tamaño del conjunto de números.

El problema de la partición de conjuntos es NP-Difícil:
para probar que el problema de conjuntos independientes es NP-Difícil, realice una reducción de un problema NP-Difícil conocido a este problema. Realice una reducción a partir de la cual el problema de la suma de subconjuntos se pueda reducir al problema de partición de conjuntos . El problema del subconjunto proporciona la entrada como un conjunto de números S y una suma objetivo t , el problema tiene como objetivo encontrar el subconjunto T que pertenece a S con una suma igual a la t . Sea s la suma de los miembros de S . Ahora, introduce S’ = S ∪ {s − 2t} en el problema de la partición de conjuntos.

Ahora demuestre que el problema de calcular la partición del conjunto se reduce al cálculo de la suma del subconjunto. La reducción puede probarse mediante las siguientes dos proposiciones:

Ahora, consideremos un conjunto de números T con suma equivalente a t (Subset Sum), luego el resto de los elementos en S (asumiendo O ) tendrán la suma o = s – t . Supongamos que el conjunto original es igual a T’ = T ∪ (s – 2t) que tiene una suma igual a t’ . 
Ahora se cumplen las siguientes observaciones:

o = s – t 
o – t = s – 2t, Diferencia en la suma entre O y T.
t’ = t + (s – 2t)
       = s – t
       = o, la suma de T’ y O son iguales.

Por lo tanto, el conjunto original se puede dividir en dos subconjuntos de suma (s – t) cada uno. Por lo tanto, se satisface el problema de la partición establecida. 
Ahora suponga que existe una partición de igual suma (A, A’) de S’ = S ∪ {s − 2t} . La suma de cada partición viene dada por:

Considere que la partición que contiene el elemento {s – 2t} es A’ . Sea A = A’- {s – 2t} . La suma de los elementos en A viene dada por:

A = s – t – {s – 2t}
   = t

Además, S’ – S = {s – 2t} . Entonces A es un subconjunto de S con una suma igual a t . 

Por lo tanto, el problema de la suma de subconjuntos se cumple.