Problema de la partición

En ciencias de la computación, el Problema de la partición es un problema NP-completo, que visto como un problema de decisión, consiste en decidir si, dado un multiconjunto de números enteros, puede este ser particionado en dos "mitades" tal que sumando los elementos de cada una, ambas den como resultado la misma suma.

Más precisamente, dado un multiconjunto S de enteros: ¿existe alguna forma de partir S en dos subconjuntos S₁ y S₂, tal que la suma de los elementos en S₁ sea igual que la suma de los elementos en S₂?

El problema de partición es equivalente a un caso particular del problema de la suma de subconjuntos, el cual dice: dado un conjunto S de enteros, ¿existe algún subconjunto S₁ de S cuyos elementos suman exactamente t /2, donde t es la suma de todos los elementos de S? La equivalencia puede verse definiendo S₂ como la diferencia S − S₁. Por lo tanto, la solución con programación dinámica existente para resolver el problema de suma de subconjuntos, utilizando tiempo pseudo-polinómico, también es aplicable al problema de partición.

Una variación de este problema es el problema de la 3-partición, en donde el conjunto S debe particionarse en |S|/3 subconjuntos que sumen lo mismo. A diferencia del problema de partición, este problema no es resoluble en tiempo pseudo-polinómico, a menos que P = NP: esto porque el problema de 3-partición permanece en la clase NP-completa incluso utilizando codificación unaria.

Véase también

• Problema de la suma de subconjuntos
• Problema de la mochila

Referencias

• The Easiest Hard Problem - artículo en American Scientist por Brian Hayes.

• Datos: Q1065968