Reducción del problema de 3 particiones a problema de partición equilibrada

13

El problema de 3 particiones pregunta si un conjunto de 3n enteros se puede dividir en n conjuntos de tres enteros, de modo que cada conjunto sume un entero dado B. El problema de Partición equilibrada pregunta si 2n enteros se pueden dividir en dos conjuntos de cardinalidad iguales de modo que ambos conjuntos tengan la misma suma. Se sabe que ambos problemas son NP completos. Sin embargo, 3-Partition es fuertemente NP-complete. No he visto en la literatura ninguna reducción de 3-Partición a Partición equilibrada.

Estoy buscando una reducción (simple) del problema de 3 particiones al problema de Particiones equilibradas.

Mohammad Al-Turkistany
fuente
Entonces, ¿desea una asignación de instancias de 3 particiones instancias de partición equilibrada? (la "meta-reducción" en la misma dirección buscaría un mapeo en la otra.)
Raphael
¿Qué es la meta reducción?
Mohammad Al-Turkistany
2
Estoy buscando la reducción de Karp del problema de 3 particiones a un problema de partición equilibrada. Espero que quede claro.
Mohammad Al-Turkistany
1
Estoy contento con las reducciones complejas.
Mohammad Al-Turkistany
2
ya que es débilmente , probablemente necesite un truco similar al de reducir 3SAT, que usará números con muchos bits. Ver Sipser por ejemplo. Y siempre puede combinar la reducción múltiple para obtener lo que desea, vea esto . NP-hard
Kaveh

Respuestas:

1

Hay miles de problemas de NP completo en la literatura, y la mayoría de los pares no tienen reducciones explícitas. Dado que las reducciones múltiples de tiempo polinómico se componen, es suficiente que los investigadores se detengan cuando el gráfico de reducciones publicadas está fuertemente conectado, lo que hace que la investigación sobre la completitud de NP sea una actividad mucho más escalable.

Aunque realmente no entiendo el punto, te seguiré haciendo una reducción razonablemente simple de 3-PARTICIÓN a PARTICIÓN EQUILIBRADA, con algunas pistas sobre cómo funciona la prueba de corrección.

Deje que la entrada a la reducción sea , una instancia de 3-PARTICIÓN. Compruebe que Σ i [ 3 n ] x i = n B . Deje que β sea ​​un gran número para ser elegido más tarde. Por cada i [ 3 n ] y cada j [ n ] , genera dos números x i β j + β n +x1,,x3n,BZi[3n]xi=nBβi[3n]j[n] Intuitivamente, el primer número significa que x i está asignado a 3 particiones j , y el segundo número significa lo contrario. El término x i β j se usa para rastrear la suma de 3 particiones j . El término β n + j se utiliza para rastrear la cardinalidad de 3 particiones j . El término β 2 n + i se utiliza para garantizar que cada x i se asigne exactamente una vez. El β (

xiβj+βn+j+β2n+i+β(i+4)n+jβ(i+4)n+j.
xijxiβjjβn+jjβ2n+ixi término n + j se usa para forzar estos números en diferentes particiones equilibradas.β(i+4)n+j

Salida dos números más El primer número identifica su partición equilibrada como "verdadera" y la otra, como "falsa". Eltérmino 1 se usa para forzar estos números en diferentes particiones equilibradas. Los otros términos constituyen la diferencia entre la suma de una partición de 3 y la suma de su complemento y el tamaño de una partición de 3 y el tamaño de su complemento y el número de veces quese asigna x i .

1+j[n]((n2)Bβj+(3n6)βn+j)+i[3n](n2)β2n+i1.
1xi

debe elegirse lo suficientemente grande como para garantizar que no se produzca un "desbordamiento".β

Herm
fuente
2
Es difícil seguir / creer su construcción sin ideas elaboradas o la prueba. ¿Puede proporcionar al menos uno de los dos?
Raphael
0

¡Este documento, Particionamiento equilibrado rápido es difícil incluso en cuadrículas y árboles , de Andreas Emil Feldmann, contiene lo que quieres! ¡Buena suerte!

Estableceremos un marco general para una reducción de 3-PARTICIÓN a diferentes clases de gráficos. Esto se logrará mediante la identificación de algunas propiedades estructurales que debe cumplir un gráfico construido a partir de una instancia de 3 PARTICIONES, para mostrar la dureza del problema de PARTICIONAMIENTO EQUILIBRADO ...k

Daniel
fuente
Este documento no tiene nada que ver con el problema que Mohammad preguntó. Este se trata de dividir los vértices de un gráfico con respecto a minimizar el número de bordes entre las particiones.
domotorp