Más precisamente, dado un multiconjunto S de enteros: ¿existe alguna forma de partir 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 diferenciaS − S1. 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.
problema, partición, ciencias, computación, problema, completo, visto, como, problema, decisión, consiste, decidir, dado, multiconjunto, números, enteros, puede, este, particionado, mitades, sumando, elementos, cada, ambas, como, resultado, misma, suma, más, p. En ciencias de la computacion el Problema de la particion es un problema NP completo que visto como un problema de decision consiste en decidir si dado un multiconjunto de numeros enteros puede este ser particionado en dos mitades tal que sumando los elementos de cada una ambas den como resultado la misma suma Mas precisamente dado un multiconjunto S de enteros existe alguna forma de partir 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 particion es equivalente a un caso particular del problema de la suma de subconjuntos el cual dice dado un conjunto S de enteros existe algun 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 solucion con programacion dinamica existente para resolver el problema de suma de subconjuntos utilizando tiempo pseudo polinomico tambien es aplicable al problema de particion Una variacion de este problema es el problema de la 3 particion en donde el conjunto S debe particionarse en S 3 subconjuntos que sumen lo mismo A diferencia del problema de particion este problema no es resoluble en tiempo pseudo polinomico a menos que P NP esto porque el problema de 3 particion permanece en la clase NP completa incluso utilizando codificacion unaria Vease tambien editarProblema de la suma de subconjuntos Problema de la mochilaReferencias editarThe Easiest Hard Problem articulo en American Scientist por Brian Hayes nbsp Datos Q1065968 Obtenido de https es wikipedia org w index php title Problema de la particion amp oldid 131227022, wikipedia, wiki, leyendo, leer, libro, biblioteca,
