- Problema de la partición
-
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 éste 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 particionar S en dos subconjuntos S1 y S2, tal que la suma de los elementos en S1 sea igual que la suma de los elementos en S2?
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 S1 de S cuyos elementos suman exactamente t /2, donde t es la suma de todos los elementos de S? La equivalencia puede verse definiendo S2 como la diferencia S − S1. Por lo tanto, la solución con programación dinámica existente para resolver el problema de suma de subconjuntos, utilizando tiempo pseudo-polinomial, también es aplicable al problema de partición.
Una variación de este problema es el problema de 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-polinomial, 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
Referencias
- The Easiest Hard Problem - artículo en American Scientist por Brian Hayes.
Categoría: Problemas NP-completos
Wikimedia foundation. 2010.
