Problema de la 3-partición

En ciencias de la computación, el Problema de 3-partición es un problema NP-completo, que consiste en decidir si dado un multiconjunto S de n = 3m enteros positivos, puede ser particionado en m subconjuntos S₁, S₂, …, S_m tal que la suma de sus elementos sea la misma.

Más precisamente, dado un multiconjunto S de 3m números enteros positivos, ¿puede S partirse en m subconjuntos S₁, S₂,..., S_m tal que la suma de los números de cada subconjunto sea igual?. Los subconjuntos S₁,S₂,..., S_m deben formar una partición de S en el sentido de que están disjuntos y cubren S.

Se puede definir la complejidad del problema de la siguiente manera:

Sea B la suma buscada de cada subconjunto S_i, o equivalentemente, sea mB la suma total de los números en S. Entonces el problema de la 3-Partición permanece dentro de NP-completo cuando cada entero de S está estrictamente entre B/2 y B/4. En este caso, cada subconjunto S_i es forzado a ser un conjunto de 3 elementos ( una tripleta ).

El problema de la 3-partición es similar al problema de la partición, que a su vez está relacionado con problema de la suma de subconjuntos. En el problema de la partición el objetivo es partir S subconjuntos que posean la misma suma. Es importante señalar que el problema de la 3-partición el objetivo es partir S en m subconjuntos (o n/3 subconjuntos), no 3 subconjuntos, con igual suma.

Carácter fuertemente NP-Completo

Lo interesante del problema es que sigue siendo NP-completo incluso cuando los enteros de S están acotados por un polinomio en n. En otras palabras, el problema permanece al conjunto de problemas NP-completo incluso cuando la representación de los números en el argumento de entrada es unaria. Es decir, el problema de la 3-partición es NP-completo en sentido estricto o estrictamente NP-completo. Esta propiedad, y en la 3-partición en general, es útil en muchas simplificaciones donde los números están representados de forma natural en unario. Por el contrario, el problema de la partición es NP-completo sólo cuando los números están codificados en binario y tienen un valor exponencial en n.

Descripción

Garey y Johnson fueron los primeros en probar que el problema de la 3-partición es NP-completo, mediante una solución de búsqueda 3-dimensional.^[1] Ambos autores también proveen una demostración de complejidad fuertemente NP-completo, reduciéndolo de la búsqueda 3-dimensional del problema de la 4-partición al de la 3-partición.^[2] El problema de la 4-partición es similar al de la 3-partición, en el que el objetivo es, dado un conjunto S, partir S en cuartetos que posean la misma suma. Precisamente, la diferencia es que S ahora consiste en n = 4m enteros, cada uno estrictamente entre B/5 y B/3.

Véase también

Referencias

↑ Garey, Michael R. y David S. Johnson (1975), Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing. (1975) Volumen 4,Páginas 397–411
↑ Garey, Michael R. y David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Páginas 96–105 y 224.

Datos: Q4634256

[1] Garey, Michael R. y David S. Johnson (1975), Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing. (1975) Volumen 4,Páginas 397–411

[2] Garey, Michael R. y David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Páginas 96–105 y 224.

[1]

[2]