Coincidencia numérica tridimensional

La correspondencia numérica tridimensional es un problema de decisión NP-completo . Está dado por tres conjuntos múltiples de números enteros , y , cada uno de los cuales contiene elementos, y un límite . El objetivo es seleccionar un subconjunto de tal que cada número entero en , y ocurra exactamente una vez y que se cumpla cada triplete en el subconjunto . Este problema está etiquetado como [SP16] en. ^[1] ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle k}$ ${\displaystyle b}$ ${\displaystyle M}$ ${\displaystyle X\times Y\times Z}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle (x,y,z)}$ ${\displaystyle x+y+z=b}$

Ejemplo

Toma , y , y . Este caso tiene una solución, a saber . Tenga en cuenta que cada triple suma . El conjunto no es una solución por varias razones: no se usan todos los números ( falta a), un número se usa con demasiada frecuencia (el ) y no todos los triples suman (desde ). Sin embargo, existe al menos una solución a este problema, que es la propiedad que nos interesa en los problemas de decisión. Si tomáramos por lo mismo , y , este problema no tendría solución (todos los números suman , que no es igual a en este caso). ${\displaystyle X=\{3,4,4\}}$ ${\displaystyle Y=\{1,4,6\}}$ ${\displaystyle Z=\{1,2,5\}}$ ${\displaystyle b=10}$ ${\displaystyle \{(3,6,1),(4,4,2),(4,1,5)\}}$ ${\displaystyle b=10}$ ${\displaystyle \{(3,6,1),(3,4,2),(4,1,5)\}}$ ${\displaystyle 4\in X}$ ${\displaystyle 3\in X}$ ${\displaystyle b}$ ${\displaystyle 3+4+2=9\neq b=10}$ ${\displaystyle b=11}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle 30}$ ${\displaystyle k\cdot b=33}$

Problemas relacionados

Cada instancia del problema de coincidencia numérica tridimensional es una instancia tanto del problema de 3 particiones como del problema de coincidencia tridimensional .

Dada una instancia de coincidencia numérica 3D, construya un hipergrafo tripartito con lados , y , donde haya un hiperborde ⁠ ⁠ si y solo si . Una coincidencia en este hipergráfico corresponde a una solución de la partición ABC. ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle (x,y,z)}$ ${\displaystyle x+y+z=T}$

Prueba de integridad NP

El problema de correspondencia numérica tridimensional es el problema [SP16] de Garey y Johnson. ^[1] Afirman que es NP-completo y se refieren a ^[2] pero la afirmación no está probada en esa fuente. La dureza NP del problema relacionado de 3 particiones se realiza en ^[1] mediante una reducción de la coincidencia tridimensional a través de 4 particiones. Para demostrar la completitud NP de la coincidencia numérica tridimensional, la prueba debe ser similar, pero se debe utilizar una reducción de la coincidencia tridimensional a través del problema de coincidencia numérica de 4 dimensiones. En artículos posteriores se ofrecen pruebas explícitas de la dureza NP:

• Yu, Hoogeveen y Lenstra ^[3] demuestran la dureza NP de una versión muy restringida de Numerical 3-Dimensional Matching, en la que dos de los tres conjuntos contienen sólo los números 1,..., k.
• Caracciolo, Fichera y Sportiello ^[4] demuestran la dureza NP de la coincidencia numérica tridimensional y problemas relacionados mediante reducción de NAE-SAT . La reducción es lineal , es decir, el tamaño de la instancia reducida es una función lineal del tamaño de la instancia original.

Referencias

1. Garey, Michael R. y David S. Johnson (1979), Computadoras e intratabilidad; Una guía para la teoría de la integridad NP. ISBN  0-7167-1045-5
2. Garey, señor; Johnson, DS (diciembre de 1975). "Resultados de complejidad para la programación multiprocesador bajo restricciones de recursos". Revista SIAM de Computación . 4 (4): 397–411. doi :10.1137/0204035. ISSN  0097-5397.
3. Yu, Wenci; Hoogeveen, Han; Lenstra, Jan Karel (1 de septiembre de 2004). "Minimizar Makespan en un taller de flujo de dos máquinas con retrasos y operaciones por unidad de tiempo es NP-Difícil". Diario de programación . 7 (5): 333–348. doi :10.1023/B:JOSH.0000036858.59787.c2. ISSN  1099-1425.
4. Caracciolo, Sergio; Fichera, Davide; Sportiello, Andrea (28 de abril de 2006), El problema de coincidencia uno entre dos es NP completo , arXiv : cs/0604113 , Bibcode : 2006cs.......4113C