Problema de la 3-partición
# 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_1,$ $S_2,$ …, $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_1,$ $S_2,...,$ $S_m$ tal que la suma de los números de cada subconjunto sea igual?. Los subconjuntos $S_1,S_2,...,$ $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. 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. 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.

