Complejidad computacional del problema de 3 particiones con números distintos

Esta pregunta está relacionada con una respuesta que publiqué en respuesta a otra pregunta.

El problema de 3 particiones es el siguiente:
Instancia : enteros positivos a ₁ , ..., a _n , donde n = 3m y la suma de los n enteros es igual a mB, de modo que cada a _i satisface B / 4 <a _i <B / 2.
Pregunta : ¿Pueden los enteros a ₁ , ..., a _n dividirse en m conjuntos múltiples para que la suma de cada conjunto múltiple sea igual a B?

Es bien sabido que el problema de 3 particiones es NP completo en el sentido estricto de que sigue siendo NP completo incluso si los números en la entrada se dan en unario. Ver Garey y Johnson para una prueba.

Preguntas : ¿El problema de 3 particiones sigue siendo NP completo si los números a ₁ , ..., a _n son todos distintos? ¿Sigue siendo NP completo en el sentido fuerte?

(Creo que las respuestas a ambas preguntas probablemente sean afirmativas porque no veo ninguna razón por la cual el problema debería ser más fácil si todos los números son distintos).

No parece que la prueba en Garey y Johnson establezca la integridad de NP de esta versión restringida.

En la respuesta a la otra pregunta vinculada anteriormente, di una prueba de que el problema de 6 particiones (definido de manera análoga) con números distintos es NP-completo en el sentido fuerte.

cc.complexity-theory np-hardness Tsuyoshi Ito
fuente

Creo que este es un problema importante; Encontré varios artículos en la literatura que afirman o asumen que la versión establecida es difícil, sin una justificación mejor que una cita a la versión de varios conjuntos en Garey y Johnson, y que usan esa suposición en un reclamo de integridad de NP para algún otro problema. .

David Eppstein

$a_1, \ldots, a_n$ $B/4 < a_i < B/2$

[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Realizaciones multigráficas de secuencias de grados: la maximización es fácil, la minimización es difícil. Oper Res. Letón. 36 (5): 594-596 (2008). DOI

Serge Gaspers
fuente

B / 4 < a_{i} < B / 2

$B/4 < a_i < B/2$

a_{i}

$a_i$

De hecho, es sencillo imponer también estos límites.

Serge Gaspers

Gracias, responde mi pregunta por completo. Tenga en cuenta que el problema parcial de finalización del cuadrado latino puede formularse fácilmente como un caso especial de la coincidencia tridimensional. No se me ocurrió reemplazar 3DM por PLSC, pero después de ver la prueba, el enfoque parece bastante natural.

Tsuyoshi Ito

Complejidad computacional del problema de 3 particiones con números distintos

Respuestas: