El problema de las 3 particiones es un problema muy NP-completo en informática . El problema es decidir si un conjunto múltiple dado de enteros se puede dividir en tripletes que tengan la misma suma. Más precisamente:
- La entrada al problema es un conjunto múltiple S de n = 3 m enteros positivos. La suma de todos los números enteros es m T .
- La salida es la de si existe o no una partición de S en m trillizos S 1 , S 2 , ..., S m tal que la suma de los números en cada uno es igual a T . El S 1 , S 2 , ..., S m debe formar una partición de S en el sentido de que son disjuntos y cubren S .
El problema de las 3 particiones permanece fuertemente NP-completo bajo la restricción de que cada entero en S está estrictamente entre T / 4 y T / 2.
Ejemplo
El conjunto S = {20, 23, 25, 30, 49, 45, 27, 30, 30, 40, 22, 19} se puede dividir en los cuatro conjuntos {20, 25, 45}, {23, 27, 40 }, {49, 22, 19}, {30, 30, 30}, cada uno de los cuales suma T = 90. Otro ejemplo; el conjunto S = {1, 2, 5, 6, 7, 9} se puede dividir en los dos conjuntos {1, 5, 9}, {2, 6, 7} cada uno de los cuales suma T = 15.
Fuerte NP-completitud
El problema de las 3 particiones sigue siendo NP-completo incluso cuando los números enteros en S están acotados arriba 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 partición 3 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 las 3 particiones es similar al problema de la partición , en el que el objetivo es dividir S en dos subconjuntos con la misma suma, y la partición numérica de múltiples vías , en el que el objetivo es dividir S en k subconjuntos con igual suma, donde k es un parámetro fijo. En 3-Partition, el objetivo es dividir S en m = n / 3 subconjuntos, no solo un número fijo de subconjuntos, con igual suma. La partición es "más fácil" que la partición 3: mientras que la partición 3 es fuertemente NP-hard , la partición solo es débilmente NP-hard ; es difícil solo cuando los números están codificados en un sistema no unario y tienen un valor exponencial en n . Cuando los valores son polinomiales en n , la partición se puede resolver en tiempo polinomial utilizando el algoritmo de partición de números de tiempo pseudopolinomial .
Variantes
En la variante de entrada sin restricciones , las entradas pueden ser 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 no restringida: dada una instancia S u de la variante no restringida, construya una nueva instancia de la versión restringida S r : = {s + 2 T | s en S u }. Toda 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 (7 T / 4, 7 T / 2).
En la variante de entrada distinta , las entradas deben estar en ( T / 4 , T / 2) y, además, todas deben ser enteros distintos. También es tan difícil como la versión sin restricciones. [1]
En la variante de salida no restringida , los subconjuntos de salida m pueden ser de tamaño arbitrario, no necesariamente 3 (pero aún deben tener la misma suma T ). La variante de salida restringida se puede reducir a la variante no restringida: dada una instancia S u de la variante restringida, construya una nueva instancia de la variante no restringida S r : = {s + 2 T | S en S u }, con suma meta 7 T . Toda solución de S u corresponde naturalmente a una solución de S r . En toda solución de S r , dado que la suma objetivo es 7 T y cada elemento está en (7 T / 4, 7 T / 2), debe haber exactamente 3 elementos por conjunto, por lo que corresponde a una solución de S u .
El problema 4-partición es una variante en la que S contiene n = 4 m números enteros, la suma de todos los números enteros es m T , y el objetivo es particionar en m cuádruples, todas con una suma de T . Se puede suponer que cada número entero está estrictamente entre T / 5 y T / 3.
El problema de la partición ABC 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 m T . El objetivo es construir m trillizos, cada uno de los cuales contiene un elemento de A, uno de B y uno de C, de manera que la suma de cada triplete es T . [2] Este problema se puede reducir a 3 particiones de la siguiente manera. Construya un conjunto S que contenga los números 1000 a +100 para cada a en A; 1000 b +10 por cada b en B; y 1000 c +1 para cada c en C. Cada solución de la instancia de partición ABC induce una solución de la instancia de 3 particiones con suma 1000 (a + b + c) +111 = 1000 T +111. Por el contrario, en cada solución de la instancia de 3 particiones, todas las sumas de tripletes deben tener los mismos dígitos de centenas, decenas y unidades, lo que significa que deben tener exactamente 1 en cada uno de estos dígitos. Por lo tanto, cada triplete debe tener exactamente un número de la forma 1000 a +100, uno 1000 b +10 y uno 1000 c +1. Por lo tanto, induce una solución a la instancia de la partición ABC.
- El problema de la partición ABC también se llama coincidencia numérica 3-d , ya que también se puede reducir al problema de coincidencia tridimensional : dada una instancia de partición ABC, construya un hipergrama tripartito con lados A, B, C, donde hay es un hyperedge (a, b, c) por cada tres vértices en a, B, C de tal manera que a + b + c = T . Una coincidencia en este hipergráfico corresponde a una solución a la partición ABC.
Pruebas
Garey y Johnson (1975) demostraron originalmente que las 3 particiones son NP completas, mediante una reducción de la coincidencia tridimensional . [3] La referencia clásica de Garey y Johnson (1979) describe una prueba de integridad NP, que se reduce de la coincidencia tridimensional a la de 4 particiones a la de 3 particiones. [4]
Aplicaciones
La dureza NP de 3 particiones se usó para probar el empaque rectangular de dureza NP , así como de Tetris [5] [6] y algunos otros acertijos, [7] y algunos problemas de programación de trabajos . [8]
Referencias
- ^ 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" . Cartas de investigación operativa . 36 (5): 594–596. doi : 10.1016 / j.orl.2008.05.004 . ISSN 0167-6377 .
- ^ Demaine, Erik (2015). "MIT OpenCourseWare - Dureza simplificada 2 - 3 particiones I" . Youtube .
- ^ Garey, Michael R. y David S. Johnson (1979), Informática e intratabilidad; Una guía para la teoría de NP-Completeness . ISBN 0-7167-1045-5 . Páginas 96–105 y 224.
- ^ Garey, Michael R. y David S. Johnson (1975). "Resultados de complejidad para la programación de multiprocesador con limitaciones de recursos". Revista SIAM de Computación . 4 (4): 397–411. doi : 10.1137 / 0204035 .
- ^ "Tetris es difícil, incluso aproximarse" . Naturaleza . 2002-10-28. doi : 10.1038 / news021021-9 . ISSN 0028-0836 .
- ^ 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 aproximado" . Revista Internacional de Geometría y Aplicaciones Computacionales . 14 (1n02): 41–68. doi : 10.1142 / s0218195904001354 . ISSN 0218-1959 .
- ^ Demaine, Erik D .; Demaine, Martin L. (1 de junio de 2007). "Rompecabezas, emparejamiento de bordes y embalaje Polyomino: conexiones y complejidad" . Gráficos y Combinatoria . 23 (S1): 195-208. doi : 10.1007 / s00373-007-0713-4 . ISSN 0911-0119 .
- ^ Bernstein, D .; Rodeh, M .; Gertner, I. (1989). "Sobre la complejidad de los problemas de programación para máquinas paralelas / canalizadas" . Transacciones IEEE en computadoras . 38 (9): 1308-1313. doi : 10.1109 / 12.29469 . ISSN 0018-9340 .