Fondo: El Exact-3D-Matching problema se define de la siguiente manera (la definición es de la nota de conferencia de Jeff: Conferencia 29: Problemas NP-Duros . También puede consulte coincidencia tridimensional ):
Exact-3D- Coincidencia: Dado un conjunto $ S $ y una colección de subconjuntos de tres elementos de $ S $, llamados triples , ¿existe una subcolección de triples disjuntos que cubren exactamente $ S $ ?
El problema 3-Partition se define como (También es de Clase 29: Problemas NP-Hard . También puede consultar el problema de 3 particiones .):
Dado un conjunto $ S $ de $ 3n $ enteros, ¿se puede dividir en $ n $ subconjuntos de tres elementos separados, de modo que cada subconjunto tenga exactamente la misma suma?
Se sabe que se puede demostrar que el problema 3-Partition es NP-completo reduciendo el NP-completo Exact-3D-Matching problema. Y la integridad NP del problema Exact-3D-Matching se demuestra reduciendo el problema 3SAT (ambos se dan en el libro Computadoras e intratabilidad: una guía para la teoría de NP-Completeness ).
Problema: Mi problema es:
Cómo demostrar la integridad NP de la
Exact-3D-Matching¿reduciendo el3-Partitionproblema?
No he encontrado ni papeles ni notas de la conferencia sobre él.
Comentarios
Respuesta
Creo que esta reducción debería funcionar:
Dada una instancia de 3 PARTICIONES: $ n $ enteros $ a_1, \ ldots, a_ {3n} $ y una suma objetivo $ B $; marcar cada número entero con un identificador único $ \ hat {a_i} $; luego construya una colección de subconjuntos de 3 elementos $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ tal que $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ y $ i_1 \ neq i_2 \ neq i_3 $ (la colección tiene $ O (n ^ 3) $ elementos).
El original El problema de 3-PARTICIONES tiene solución si y solo si existe un $ C_ {j_1}, \ ldots, C_ {j_n} $ EXACT-3D-MATCHING que cubre $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
Por ejemplo, dado $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ construimos: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ y la colección de subconjuntos de 3 elementos:
C1 = { 5a, 2a, 1a } C2 = { 5a, 2a, 1b } C3 = { 5a, 2b, 1a } C4 = { 5a, 2b, 1b } C5 = { 4a, 3a, 1a } C6 = { 4a, 3a, 1b } C7 = { 4a, 3b, 1a } C8 = { 4a, 3b, 1b } C9 = { 4a, 3c, 1a } C10 = { 4a, 3c, 1b } C11 = { 4a, 2a, 2b } C12 = { 3a, 3b, 2a } C13 = { 3a, 3b, 2b } C14 = { 3a, 3c, 2a } C15 = { 3a, 3c, 2b } C16 = { 3b, 3c, 2a } C17 = { 3b, 3c, 2b } Una coincidencia exacta en 3D viene dada por:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } que también identifica de forma única una solución válida para el problema original de 3 PARTICIONES .
Comentarios
- Sí, funciona. No pude marcar cada $ a_i $ como único. Gracias.
Exact-3D-Matchinga3-Partitionse puede encontrar fácilmente (aunque la reducción en sí no es fácil) en los libros de texto. Por lo tanto, pido la dirección inversa. Cambiaré el título y aceptaré su respuesta.