Problema de la partició

En ciències de la computació, el Problema de la partició és un problema NP-complet, que vist com un problema de decisió, consistix en decidir si, donat un multiconjunto d'número entero, pugues este ser particionado en dos "mitats" tal que sumant els elements de cada una, abdós donen com resultat la mateixa suma.

Més precisament, donat un multiconjunto S de sancers: ¿existix alguna forma de partir S en dos subconjunts S₁ i S₂, tal que la suma dels elements en S₁ siga igual que la suma dels elements en S₂?

El problema de partició és equivalent a un cas particular del problema de la suma de subconjunts, el qual diu: donat un conjunt S de sancers, ¿existix algun subconjunt S₁ de S els elements de la qual sumen exactament t /2, a on t és la suma de tots els elements de S? L'equivalència pot vore's definint S₂ com la diferencia S − S₁. Per lo tant, la solució en programació dinàmica existent per a resoldre el problema de suma de subconjunts, utilisant temps pseudo-polinòmic, també és aplicable al problema de partició.

Una variació d'este problema és el problema de la 3-partició, en a on el conjunt S deu particionarse en |S|/3 subconjunts que sumixen lo mateix. A diferència del problema de partició, este problema no és resoluble en temps pseudo-polinòmic, a menos que P = NP: açò perque el problema de 3-partició permaneix en la classe NP-completa inclús utilisant codificació unaria.

Vore també

• Problema de la suma de subconjunts
• Problema de la mochila

Referències

• The Easiest Hard Problem - artícul en American Scientist per Brian Hayes.