Correspondencia tridimensional numérica

El emparejamiento tridimensional numérico es un problema de decisión NP-completo . Está dado por tres conjuntos múltiples de 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 para cada triple en el subconjunto se mantenga. Este problema está etiquetado como [SP16] en. ^[1] ${\ estilo de visualización X}$ ${\ estilo de visualización Y}$ ${\ estilo de visualización Z}$ ${\ estilo de visualización k}$ ${\ estilo de visualización b}$ ${\ estilo de visualización M}$ ${\ estilo de visualización X \ veces Y \ veces Z}$ ${\ estilo de visualización X}$ ${\ estilo de visualización Y}$ ${\ estilo de visualización Z}$ ${\ estilo de visualización (x, y, z)}$ ${\ estilo de visualización x + y + z = b}$

Toma , y , y . Esta instancia 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 que ). Sin embargo, hay al menos una solución a este problema, que es la propiedad que nos interesa con los problemas de decisión. Si tomáramos por igual , y , este problema no tendría solución (todos los números suman , que en este caso no es igual). $X=\{3,4,4\}$ $Y=\{1,4,6\}$ $Z=\{1,2,5\}$ ${\ estilo de visualización b = 10}$ ${\ estilo de visualización \ {(3,6,1), (4,4,2), (4,1,5) \}}$ ${\ estilo de visualización b = 10}$ ${\ estilo de visualización \ {(3,6,1), (3,4,2), (4,1,5) \}}$ ${\ estilo de visualización 4 \ en X}$ ${\ estilo de visualización 3 \ en X}$ ${\ estilo de visualización b}$ ${\ estilo de visualización 3 + 4 + 2 = 9 \ neq b = 10}$ ${\ estilo de visualización b = 11}$ ${\ estilo de visualización X}$ ${\ estilo de visualización Y}$ ${\ estilo de visualización Z}$ ${\ estilo de visualización 30}$ $k\cdot b=33$