Problema de 3 particiones

El problema de la partición triple es un problema fuertemente NP-completo en informática . El problema consiste en decidir si un conjunto múltiple dado de números enteros se puede dividir en tripletes que tengan todos la misma suma. Más precisamente:

• Entrada: un multiconjunto S que contiene n elementos enteros positivos.
• Condiciones: S debe ser particionable en m tripletes, S ₁ , S ₂ , …, S _m , donde n = 3m . Estos tripletes particionan a S en el sentido de que son disjuntos y cubren a S . El valor objetivo T se calcula tomando la suma de todos los elementos en S , luego dividida por m .
• Salida: si existe o no una partición de S tal que, para todos los tripletes, la suma de los elementos en cada triplete sea igual a T.

El problema de la partición triple sigue siendo fuertemente NP-completo bajo la restricción de que cada entero en S está estrictamente entre T /4 y T /2.

Ejemplo

1. El conjunto se puede dividir en cuatro conjuntos , cada uno de los cuales suma T = 90. ${\displaystyle S=\{20,23,25,30,49,45,27,30,30,40,22,19\}}$ ${\displaystyle \{20,25,45\},\{23,27,40\},\{49,22,19\},\{30,30,30\}}$
2. El conjunto se puede dividir en dos conjuntos, cada uno de los cuales suma T = 15. ${\displaystyle S=\{1,2,5,6,7,9\}}$ ${\displaystyle \{1,5,9\},\{2,6,7\}}$
3. (cada entero en S está estrictamente entre T /4 y T /2): , por lo tanto m = 2 y T = 15. Existe una partición tripartita factible . ${\displaystyle S=\{4,5,5,5,5,6\}}$ ${\displaystyle \{4,5,6\},\{5,5,5\}}$
4. (todo entero en S está estrictamente entre T /4 y T /2): , por lo tanto m = 2 y T = 15. No hay solución factible. ${\displaystyle S=\{4,4,4,6,6,6\}}$

NP-completitud fuerte

El problema de 3-partición sigue siendo NP-completo incluso cuando los números enteros en S están acotados por encima por un polinomio en n . En otras palabras, el problema sigue siendo NP-completo incluso cuando se representan los números en la instancia de entrada en unario. es decir, la 3-partición es NP-completa en el sentido fuerte o fuertemente NP-completa . Esta propiedad, y la 3-partición en general, es útil en muchas reducciones donde los números se representan naturalmente en unario.

3-Partición vs Partición

El problema de 3-partición es similar al problema de partición , en el que el objetivo es particionar S en dos subconjuntos con suma igual, y al particionamiento de números multidireccional , en el que el objetivo es particionar S en k subconjuntos con suma igual, donde k es un parámetro fijo. En 3-Partición el objetivo es particionar S en m = n /3 subconjuntos, no solo un número fijo de subconjuntos, con suma igual. La partición es "más fácil" que la 3-Partición: mientras que la 3-Partición es fuertemente NP-hard , la Partición es solo débilmente NP-hard - es difícil solo cuando los números están codificados en un sistema no unario, y tienen valor exponencial en n . Cuando los valores son polinomiales en n , la Partición se puede resolver en tiempo polinomial usando el algoritmo de partición de números en tiempo pseudopolinomial .

Variantes

En la variante de entrada sin restricciones , las entradas pueden ser números enteros arbitrarios; en la variante de entrada restringida , las entradas deben estar en ( T /4 , T /2 ). La versión restringida es tan difícil como la versión sin restricciones: dada una instancia S _u de la variante sin restricciones, construya una nueva instancia de la versión restringida S _r ≔ {s + 2  T   | s ∈ S _u }. Cada solución de S _u corresponde a una solución de S _r pero con una suma de 7  T   en lugar de T , y cada elemento de S _r está en [2  T  , 3  T  ] que está contenido en ( T  /4, 7  T  /2 )  .

En la variante con entradas distintas , las entradas deben estar en ( T /4 , T /2) y, además, todas deben ser números enteros distintos. También es tan difícil como la versión sin restricciones. ^[1]

En la variante de salida sin restricciones , los m subconjuntos de salida pueden ser de tamaño arbitrario - no necesariamente 3 (pero aún necesitan tener la misma suma T ). La variante de salida restringida puede reducirse a la variante sin restricciones: dada una instancia S _r de la variante restringida, con 3 m elementos que suman mT , construya una nueva instancia de la variante sin restricciones S _u ≔ {s + 2 T | s ∈ S _r }, con 3m elementos que suman 7mT, y con suma objetivo 7  T  . Cada solución de S _r corresponde naturalmente a una solución de S _u . A la inversa, en cada solución de S _u , dado que la suma objetivo es 7  T   y cada elemento está en ( T  /4, 7  T  /2 )  , debe haber exactamente 3 elementos por conjunto, por lo que corresponde a una solución de S _r .

El problema de partición ABC (también llamado emparejamiento numérico tridimensional ) es una variante en la que, en lugar de un conjunto S con 3  m   enteros, hay tres conjuntos A , B , C con m enteros en cada uno. La suma de los números en todos los conjuntos es ⁠ ⁠ ${\displaystyle mT}$ . El objetivo es construir m tripletes, cada uno de los cuales contiene un elemento de A, uno de B y uno de C, de modo que la suma de cada triplete sea T . ^[2]

El problema de 4 particiones es una variante en la que S contiene n = 4  m   enteros, la suma de todos los enteros es ⁠ ⁠ ${\displaystyle mT}$ , y el objetivo es particionarlo en m cuatrillizos, todos con una suma de T . Se puede suponer que cada entero está estrictamente entre T /5 y T /3. De manera similar, ABCD-partition es una variante de 4 particiones en la que cada uno de los 4 conjuntos de entrada y cada cuatrillizo debe contener un elemento de cada conjunto.

Pruebas

Garey y Johnson (1975) demostraron originalmente que la partición tridimensional es NP-completa, mediante una reducción a partir de una correspondencia tridimensional . ^[3] La referencia clásica de Garey y Johnson (1979) describe una prueba de NP-completitud, reduciendo desde una correspondencia tridimensional a una partición cuádruple y luego a una partición tridimensional. ^[4] Lógicamente, la reducción se puede dividir en varios pasos.

Reducción de la correspondencia 3D a la partición ABCD

Se nos da una instancia de E de correspondencia 3d, que contiene algunos m tripletes {w _i ,x _j ,y _k }, donde los vértices son w ₁ ,...,w _q y x ₁ ,...,x _q e y ₁ ,...,y _q . Construimos una instancia de partición ABCD con 4* m elementos, de la siguiente manera (donde r := 32q):

• Para cada triplete t = {w _i ,x _j ,y _k } en E, el conjunto A contiene un elemento u _t = 10r ⁴ -kr ³ -jr ² -ir.
• Para cada triplete t = {w _i ,x _j ,y _k } en E, el conjunto B contiene a w _it , C contiene a x _jt y D contiene a y _kt . Por lo tanto, para cada uno de w _i , x _j , y _k , puede haber muchos elementos correspondientes en B, C, D - uno por cada triplete en el que aparecen. Consideramos uno de estos elementos (indicado por "1") como el "real" y los demás como "ficticios". Los tamaños de los elementos son los siguientes:
  • w _i [1] = 10r ⁴ + ir; w _i [2..] = 11r ⁴ + ir.
  • x _j [1] = 10r ⁴ + jr ² ; x _j [2..] = 11r ⁴ + jr ² .
  • y _k [1] = 10r ⁴ +kr ³ ; y _k [2..] = 8r ⁴ +kr ³ .
• La suma de cada tres elementos "reales" o de cada tres elementos "ficticios" es 30r ⁴ + ir + jr ² + kr ³ ; y si se suma el elemento triplete, la suma es 40r ⁴ .
• El umbral para la instancia de partición ABCD es T=40r ⁴ . Tenga en cuenta que el tamaño de cada elemento está en (T/3,T/5).

Dado un emparejamiento perfecto en E , construimos una partición de 4 de ABCD de la siguiente manera:

• Para cada triplete t= { w _i ,x _j ,y _k } en el emparejamiento, construimos un conjunto de 4 {u _t , w _i [1], x _j [1], y _k [1]}.
• Para cada triplete que no esté en la correspondencia, construimos un conjunto de 4 similar, pero con los elementos ficticios correspondientes.

En ambos casos la suma de los 4 conjuntos es 40r ⁴ según sea necesario.

Dada una partición de ABCD, la suma de cada conjunto de 4 es 40r ⁴ . Por lo tanto, los términos con r, r ² y r ³ deben cancelarse, y los términos con r ⁴ deben sumar 40r ⁴ ; por lo tanto, el conjunto de 4 debe contener un triplete y 3 elementos "reales" coincidentes, o un triplete y 3 elementos "ficticios" coincidentes. A partir de los tripletes con los 3 elementos "reales" coincidentes, construimos un emparejamiento perfecto válido en E.

Tenga en cuenta que, en la reducción anterior, el tamaño de cada elemento es polinomial en el tamaño de entrada; por lo tanto, esta reducción muestra que la partición ABCD es fuertemente NP-dura.

Reducción de partición ABCD a partición 4

Dada una instancia de partición ABCD con m elementos por conjunto, umbral T y suma mT , construimos una instancia de partición 4 con 4 m elementos:

• Para cada elemento a en A, el elemento correspondiente tiene tamaño 16a+1;
• Para cada elemento b en B, el elemento correspondiente tiene tamaño 16b+2;
• Para cada elemento c en C, el elemento correspondiente tiene tamaño 16c+4;
• Para cada elemento d en D, el elemento correspondiente tiene tamaño 16d+8.

En total, la suma es 16mT+15m, y el nuevo umbral es 16T+15.

Toda partición ABCD corresponde naturalmente a una partición 4. A la inversa, en toda partición 4, la suma módulo 16 es 15 y, por lo tanto, debe contener exactamente un elemento con un tamaño módulo 16 = 1, 2, 4, 8; esto corresponde exactamente a un elemento de A, B, C, D, a partir del cual podemos construir una partición ABCD.

Utilizando una reducción similar, la partición ABC se puede reducir a una partición de 3.

Reducción de 4 particiones a 3 particiones

Se nos da una instancia A de 4-partición: 4 m enteros, a ₁ ,...,a _4m , cada uno de los cuales está en el rango (T/3,T/5), y su suma total es mT . Construimos una instancia B de 3-partición de la siguiente manera:

• Para cada a _i en A, B contiene un elemento "regular" w _i = 4*(5T+a _i )+1. En total hay 4 m elementos regulares, que suman 81mT + 4m.
• Para cada par de elementos a _i ,a _j en A, B contiene dos elementos "de apareamiento": u _ij = 4*(6T - a _i - a _j )+2 y u _ij ' = 4*(5T + a _i + a _j )+2. En total hay 4 m* (4 m -1) elementos de apareamiento, que suman (88mT+16m)*(4 m -1).
• Además, B contiene ^8m2-3m elementos "de relleno", con tamaño 20T, y suma total (8m2-3m ⁾ *20T.
• En total, B contiene 24m ² -3m = 3(8m ² -m) elementos, con suma (64T+4)*(8m ² -m).
• El umbral para la instancia de 3 particiones es 64T+4; tenga en cuenta que los tamaños de todos los elementos en B están en (16T+1,32T+2).

Dada una partición 4-de A , construimos una partición 3-de B de la siguiente manera:

• Para cada conjunto de 4 {a ₁ ,a ₂ ,a ₃ ,a ₄ } con suma T, construimos un conjunto de 3 {w ₁ ,w ₂ ,u ₁₂ } con suma 4*(5T+a ₁ +5T+a ₂ +6T-a ₁ -a ₂ )+1+1+2=64T+4 y otro conjunto de 3 {w ₃ ,w ₄ ,u ₁₂ '} con suma 4*(5T+a ₃ +5T+a ₄ +5T+a ₁ +a ₂ )+1+1+2=64T+4. Estos conjuntos contienen los 4m elementos regulares y 2m pares coincidentes de elementos de emparejamiento.
• A partir de los elementos restantes, construimos 3-conjuntos {u _ij ,u _ij ',filler} con suma 4*(6T-a _i -a _j +5T+a _i +a _j +5T)+2+2=64T+4.

Por el contrario, dada una partición tridimensional de B, la suma de cada conjunto tridimensional es un múltiplo de 4, por lo que debe contener dos elementos regulares y un elemento de emparejamiento, o dos elementos de emparejamiento y un elemento de relleno:

• Si un conjunto de 3 contiene dos elementos de emparejamiento u _ij , u _kl y un elemento de relleno, entonces la suma de los dos elementos de emparejamiento debe ser 44T+4 = 4*(5T+6T)+2+2, por lo que deben tener tamaños coincidentes (a _i + a _j = a _k + a _l ). Por lo tanto, al reemplazar según sea necesario, podemos suponer que los dos elementos de emparejamiento son de hecho u _ij y u _ij '. Por lo tanto, los elementos de emparejamiento restantes también constan de n pares coincidentes.
• Por lo tanto, los 3-conjuntos restantes se pueden dividir en dos grupos: n 3-conjuntos que contienen los elementos u _ij , y n 3-conjuntos que contienen los elementos u _ij '. En cada par coincidente de 3-conjuntos, la suma de los dos elementos de emparejamiento u _ij +u _ij ' es 44T+4, por lo que la suma de los cuatro elementos regulares es 84T+4. Por lo tanto, a partir de los cuatro elementos regulares, construimos un 4-conjunto en A, con suma T.

Aplicaciones

La dureza NP de la partición 3 se utilizó para probar el empaquetamiento de rectángulos de dureza NP , así como de Tetris ^{[5] [6]} y algunos otros rompecabezas, ^[7] y algunos problemas de programación de trabajos . ^[8]

Referencias

1. Hulett, Heather; Will, Todd G.; Woeginger, Gerhard J. (1 de septiembre de 2008). "Realizaciones multigráficas de secuencias de grados: la maximización es fácil, la minimización es difícil". Operations Research Letters . 36 (5): 594–596. doi :10.1016/j.orl.2008.05.004. ISSN  0167-6377.
2. Demaine, Erik (2015). "MIT OpenCourseWare - Hardness made Easy 2 - 3-Partition I". Youtube . Archivado desde el original el 14 de diciembre de 2021.
3. Garey, Michael R. y David S. Johnson (1975). "Resultados de complejidad para la programación de multiprocesadores bajo restricciones de recursos". Revista SIAM de Computación . 4 (4): 397–411. doi :10.1137/0204035.
4. Garey, Michael R. y David S. Johnson (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . ISBN 0-7167-1045-5 . Páginas 96–105 y 224. 
5. "El Tetris es difícil, incluso de aproximarse". Nature . 2002-10-28. doi :10.1038/news021021-9. ISSN  0028-0836.
6. BREUKELAAR, RON; DEMAINE, ERIK D.; HOHENBERGER, SUSAN; HOOGEBOOM, HENDRIK JAN; KOSTERS, WALTER A.; LIBEN-NOWELL, DAVID (1 de abril de 2004). "Tetris es difícil, incluso de aproximar". Revista internacional de geometría computacional y aplicaciones . 14 (1n02): 41–68. arXiv : cs/0210020 . doi :10.1142/s0218195904001354. ISSN  0218-1959. S2CID  1177.
7. Demaine, Erik D.; Demaine, Martin L. (1 de junio de 2007). "Rompecabezas, emparejamiento de aristas y empaquetamiento de poliominós: conexiones y complejidad". Graphs and Combinatorics . 23 (S1): 195–208. doi :10.1007/s00373-007-0713-4. ISSN  0911-0119. S2CID  17190810.
8. Bernstein, D.; Rodeh, M.; Gertner, I. (1989). "Sobre la complejidad de los problemas de planificación para máquinas paralelas/en cadena". IEEE Transactions on Computers . 38 (9): 1308–1313. doi :10.1109/12.29469. ISSN  0018-9340.