Problema de partición

En teoría de números e informática , el problema de partición _, o partición de números _, [ ^{1 ] consiste} en decidir si un multiconjunto S de enteros positivos dado puede particionarse en dos subconjuntos S₁ y S₂ tales que la suma de los números en S₁ sea igual a la suma de los números en S₂ _. Aunque el problema de partición es NP-completo , existe una solución de programación dinámica _en tiempo pseudopolinomial , y existen heurísticas que resuelven el problema en muchos casos, ya sea de forma óptima o aproximada. Por esta razón, se le ha llamado "el problema difícil más fácil". ^{[ 2 ] [ 3 ]}

Existe una versión de optimización _del problema de partición, que consiste en particionar el multiconjunto S en dos subconjuntos S₁ _y S₂ de manera que se minimice la diferencia entre la suma de los elementos de _S₁ y la suma de los elementos de _S₂ . Esta versión de optimización es NP-difícil , pero puede resolverse eficientemente en la práctica. ^{[ 4 ]}

El problema de partición es un caso especial de dos problemas relacionados:

• En el problema de la suma de subconjuntos , el objetivo es encontrar un subconjunto de S cuya suma sea un cierto número objetivo T dado como entrada (el problema de partición es el caso especial en el que T es la mitad de la suma de S ).
• En la partición de números multivariados , hay un parámetro entero k , y el objetivo es decidir si S se puede particionar en k subconjuntos de igual suma (el problema de partición es el caso especial en el que k = 2).

Sin embargo, es bastante diferente al problema de la partición en 3 : en ese problema, el número de subconjuntos no está fijo de antemano; debe ser | S |/3, donde cada subconjunto debe tener exactamente 3 elementos. La partición en 3 es mucho más difícil que la partición; no tiene un algoritmo de tiempo pseudopolinomial a menos que P = NP . ^{[ 5 ]}

Dado S = {3,1,1,2,2,1}, una solución válida al problema de partición son los dos conjuntos S ₁ = {1,1,1,2} y S ₂ = {2,3}. La suma de ambos conjuntos es 5, y particionan S . Esta solución no es única. S ₁ = {3,1,1} y S ₂ = {2,2,1} es otra solución.

No todo multiconjunto de enteros positivos tiene una partición en dos subconjuntos con suma igual. Un ejemplo de tal conjunto es S = {2,5}.

El problema de partición es NP-difícil. Esto se puede demostrar mediante una reducción del problema de suma de subconjuntos . ^{[ 6 ]} Una instancia de SubsetSum consiste en un conjunto S de enteros positivos y una suma objetivo T ; el objetivo es decidir si existe un subconjunto de S con suma exactamente T. 

Dado un ejemplo de este tipo, construya una instancia de Partition en la que el conjunto de entrada contenga el conjunto original más dos elementos: z ₁ y z ₂ , con z ₁  =  sum(S) y z ₂ =  2 T . La suma de este conjunto de entrada es sum( S )  + z ₁ + z ₂ = 2 sum( S ) + 2 T , por lo que la suma objetivo para Partition es sum( S ) + T .          

• Supongamos que existe una solución S ′ para la instancia SubsetSum. Entonces sum( S ′ ) = T , por lo que sum(S ′ ∪ z ₁ ) = sum( S ) + T , por lo que S ′ ∪ z ₁ es una solución para la instancia Partition.        
• Por el contrario, supongamos que existe una solución S ' ' para la instancia Partition. Entonces, S ' ' debe contener z1 o _z2 , pero no ambos, ya que su suma es mayor que sum( S ) + T. Si S '' contiene z1 , entonces debe contener elementos de S con una suma exactamente igual a _T , por lo que S '' menos z1 _es una solución para la instancia SubsetSum. Si S '' contiene z2 , entonces debe contener elementos de S con una suma exactamente igual a sum( _S ) - T , por lo _que los demás objetos en S son una solución para la instancia SubsetSum.     

Como se mencionó anteriormente, el problema de partición es un caso especial de partición múltiple y de suma de subconjuntos. Por lo tanto, puede resolverse mediante algoritmos desarrollados para cada uno de estos problemas. Los algoritmos desarrollados para la partición de números múltiples incluyen:

• Particionamiento voraz de números : itera sobre los números y coloca cada número en el conjunto cuya suma actual sea la más pequeña. Si los números no están ordenados, el tiempo de ejecución es O( n ) y la razón de aproximación es como máximo 3/2 ("razón de aproximación" significa la suma mayor en la salida del algoritmo, dividida por la suma mayor en una partición óptima). Ordenar los números aumenta el tiempo de ejecución a O( n  log n ) y mejora la razón de aproximación a 7/6. Si los números están distribuidos uniformemente en [0,1], la razón de aproximación es como máximo ${\textstyle 1+O\left({\frac {\log \log n}{n}}\right)}$casi con seguridad , y${\textstyle 1+O\left({\frac {1}{n}}\right)}$con expectativa.
• El método de diferencia más grande (también llamado algoritmo de Karmarkar-Karp ) ordena los números en orden descendente y reemplaza repetidamente los números por sus diferencias. La complejidad temporal es O( n  log n ). En el peor de los casos, su razón de aproximación es similar, como máximo 7/6 . Sin embargo, en el caso promedio, funciona mucho mejor que el algoritmo voraz : cuando los números se distribuyen uniformemente en [0,1], su razón de aproximación es como máximo ${\textstyle 1+1/n^{\Theta (\log n)}}$En previsión de ello, también ofrece mejores resultados en experimentos de simulación.
• El algoritmo multifit utiliza una búsqueda binaria combinada con un algoritmo de empaquetamiento de contenedores . En el peor de los casos, su razón de aproximación es 8/7 .
• El problema de la suma de subconjuntos tiene un FPTAS que también se puede utilizar para el problema de partición, estableciendo la suma objetivo en sum( S )/2.

Existen algoritmos exactos que siempre encuentran la partición óptima. Dado que el problema es NP-difícil, dichos algoritmos pueden requerir un tiempo exponencial en general, pero pueden ser prácticamente utilizables en ciertos casos. Los algoritmos desarrollados para la partición de números en múltiples vías incluyen:

• La partición del número de tiempo pseudopolinomial toma${\textstyle O(n^{2}m)}$tiempo y necesidades${\textstyle O(nm)}$memoria, donde m es el número más grande en la entrada.
• El algoritmo voraz completo (CGA) considera todas las particiones mediante la construcción de un árbol binario . Cada nivel del árbol corresponde a un número de entrada, donde la raíz corresponde al número más grande, el nivel inferior al siguiente número más grande, etc. Cada rama corresponde a un conjunto diferente en el que se puede colocar el número actual. Recorrer el árbol en orden de búsqueda en profundidad requiere solo${\textstyle O(n)}$espacio, pero podría tomar${\textstyle O(2^{n})}$tiempo. El tiempo de ejecución se puede mejorar utilizando una heurística voraz: en cada nivel, primero se desarrolla la rama en la que el número actual se coloca en el conjunto con la suma más pequeña. Este algoritmo encuentra primero la solución hallada por la partición voraz de números , pero luego procede a buscar mejores soluciones. Algunas variaciones de esta idea son esquemas de aproximación totalmente polinomiales para el problema de la suma de subconjuntos y, por lo tanto, también para el problema de partición. ^{[ 7 ] [ 8 ]}
• El algoritmo completo de Karmarkar-Karp (CKK) considera todas las particiones mediante la construcción de un árbol binario. Cada nivel corresponde a un par de números. La rama izquierda corresponde a colocarlos en subconjuntos diferentes (es decir, reemplazarlos por su diferencia), y la rama derecha corresponde a colocarlos en el mismo subconjunto (es decir, reemplazarlos por su suma). Este algoritmo encuentra primero la solución hallada por el método de diferenciación más grande , pero luego procede a encontrar mejores soluciones. Se ejecuta sustancialmente más rápido que CGA en instancias aleatorias. Su ventaja es mucho mayor cuando existe una partición igual, y puede ser de varios órdenes de magnitud. En la práctica, CKK puede resolver problemas de tamaño arbitrario si los números tienen como máximo 12 dígitos significativos . ^{[ 9 ]} CKK también puede ejecutarse como un algoritmo en cualquier momento : primero encuentra la solución KK, y luego encuentra soluciones progresivamente mejores a medida que el tiempo lo permite (posiblemente requiriendo un tiempo exponencial para alcanzar la optimalidad, para las peores instancias). ^{[ 1 ]} Requiere$En)$espacio, pero en el peor de los casos podría ocupar$O(2^{n})$tiempo.

Los algoritmos desarrollados para la suma de subconjuntos incluyen:

• Horowitz y Sanhi – corren a tiempo$O(2^{n/2}\cdot (n/2))$pero requiere$O(2^{n/2})$espacio.
• Schroeppel y Shamir – corre a tiempo $O(2^{n/2}\cdot (n/4))$y requiere mucho menos espacio –${\textstyle O(2^{n/4})}$.
• Howgrave-Graham y Joux – se ejecuta en tiempo real${\textstyle O(2^{n/3})}$, pero es un algoritmo aleatorio que solo resuelve el problema de decisión (no el problema de optimización).

Los conjuntos con una sola partición, o sin particiones, tienden a ser los más difíciles (o más costosos) de resolver en comparación con sus tamaños de entrada. Cuando los valores son pequeños en comparación con el tamaño del conjunto, es más probable que existan particiones perfectas. Se sabe que el problema experimenta una " transición de fase "; siendo probable para algunos conjuntos e improbable para otros. Si m es el número de bits necesarios para expresar cualquier número en el conjunto y n es el tamaño del conjunto, entonces${\displaystyle m/n<1}$tiende a tener muchas soluciones y${\displaystyle m/n>1}$Suele tener pocas o ninguna solución. A medida que n y m aumentan, la probabilidad de una partición perfecta tiende a 1 o 0 respectivamente. Esto fue argumentado originalmente con base en evidencia empírica por Gent y Walsh, ^{[ 10 ]} luego utilizando métodos de física estadística por Mertens, ^{[ 11 ] [ 12 ]} y posteriormente demostrado por Borgs , Chayes y Pittel . ^{[ 13 ]}

Un problema relacionado, similar a la paradoja del cumpleaños , consiste en determinar el tamaño del conjunto de entrada de manera que exista una probabilidad de un medio de que haya una solución, bajo el supuesto de que cada elemento del conjunto se selecciona aleatoriamente con una distribución uniforme entre 1 y un valor dado. La solución a este problema puede resultar contraintuitiva, al igual que la paradoja del cumpleaños.

La partición de cardinalidad igual es una variante en la que ambas partes deben tener un número igual de elementos, además de tener una suma igual. Esta variante también es NP-difícil. ^{[ 5 ] : SP12} Demostración . Dada una instancia estándar de Partición con algunos n números, construya una instancia de Partición de Cardinalidad Igual agregando n ceros. Claramente, la nueva instancia tiene una partición de cardinalidad igual y suma igual si y solo si la instancia original tiene una partición de suma igual. Véase también Particionamiento de números equilibrado .

La partición de productos es el problema de particionar un conjunto de enteros en dos conjuntos con el mismo producto (en lugar de la misma suma). Este problema es fuertemente NP-difícil . ^{[ 14 ]}

Kovalyov y Pesch ^{[ 15 ]} discuten un enfoque genérico para demostrar la NP-dificultad de los problemas de tipo partición.

Una aplicación del problema de partición es la manipulación de elecciones . Supongamos que hay tres candidatos (A, B y C). Se debe elegir un único candidato mediante una regla de votación basada en puntuación, por ejemplo, la regla del veto (cada votante veta a un candidato y gana el candidato con menos vetos). Si una coalición quiere asegurar la elección de C, debe dividir sus votos entre A y B para maximizar el menor número de vetos que recibe cada uno. Si los votos están ponderados, el problema se reduce al problema de partición y, por lo tanto, se puede resolver de manera eficiente utilizando CKK. Lo mismo ocurre con cualquier otra regla de votación basada en puntuación. ^{[ 16 ]}

• Borgs, Christian; Chayes, Jennifer; Pittel, Boris (2001), "Transición de fase y escalamiento de tamaño finito para el problema de partición de enteros", Random Structures and Algorithms , 19 ( 3–4 ): 247–288 , CiteSeerX 10.1.1.89.9577 , doi : 10.1002/rsa.10004 , S2CID 6819493  
• Gent, Ian; Walsh, Toby (agosto de 1996). "Transiciones de fase y teorías recocidas: la partición de números como estudio de caso". En Wolfgang Wahlster (ed.). Actas de la 12.ª Conferencia Europea sobre Inteligencia Artificial . ECAI-96. John Wiley and Sons. págs. 170–174 . CiteSeerX 10.1.1.2.4475 .  
• Gent, Ian; Walsh, Toby (1998), "Análisis de heurísticas para la partición de números", Inteligencia Computacional , 14 (3): 430– 451, CiteSeerX 10.1.1.149.4980 , doi : 10.1111/0824-7935.00069 , S2CID 15344203  
• Korf, Richard E. (1998), "Un algoritmo completo para particionamiento de números en cualquier momento", Inteligencia Artificial , 106 (2): 181– 203, CiteSeerX 10.1.1.90.993 , doi : 10.1016/S0004-3702(98)00086-1 , ISSN 0004-3702  
• Mertens, Stephan (noviembre de 1998), "Transición de fase en el problema de partición de números", Physical Review Letters , 81 (20): 4281–4284 , arXiv : cond-mat/9807077 , Bibcode : 1998PhRvL..81.4281M , doi : 10.1103/PhysRevLett.81.4281 , S2CID 119541289 
• Mertens, Stephan (2001), "Un enfoque físico para la partición de números", Theoretical Computer Science , 265 ( 1–2 ): 79–108 , arXiv : cond-mat/0009230 , doi : 10.1016/S0304-3975(01)00153-0 , S2CID 16534837 
• Mertens, Stephan (2006). «El problema difícil más fácil: la partición de números» . En Allon Percus; Gabriel Istrate; Cristopher Moore (eds.). Complejidad computacional y física estadística . EE. UU.: Oxford University Press. pp. 125–140 . arXiv : cond-mat/0310317 . Bibcode : 2003cond.mat.10317M . ISBN  9780195177374.
• Mertens, Stephan (1999), "Un algoritmo completo para cualquier momento para la partición equilibrada de números", arXiv : cs/9903011