Correspondência numérica 3-dimensional

Correspondência numérica 3-dimensional é um problema de decisão NP-completo. Ela é dada por três multisets de inteiros $X$, $Y$ and $Z$, cada um contendo $k$ elementos , e um limitante $b$ vinculado. O objetivo é selecionar um subconjunto $M$ de $X\times Y\times Z$ tal que todo inteiro em $X$, $Y$ and $Z$ ocorre apenas uma vez e que, para cada tripla $(x,y,z)$ no subconjunto de$x+y+z=b$ se mantenha . Este problema é rotulado como [ SP16 ] em.

Exemplos

Pegue um $X=\{3,4,4\}$, $Y=\{1,4,6\}$ e$Z=\{1,2,5\}$, e $b=10$. Este exemplo tem uma solução, ou seja, $\{(3,6,1),(4,4,2),(4,1,5)\}$. Note-se que cada somas tripla para $b=10$. O conjunto $\{(3,6,1),(3,4,2),(4,1,5)\}$ não é uma solução, por diversas razões: nem todo o número é usado $4\in X$ está ausente), um número é usado com muita freqüência ($3\in X$) e nem toda tripla se soma à $b$ (desde $3+4+2=9\ne b=10$). No entanto, existe pelo menos uma solução para este problema, que é a propriedade que nos interessa dos problemas de decisão. Se nós atribuíssemos $b=11$ para o mesmo $X$, $Y$ e $Z$, este problema teria nenhuma solução (todos os números de somam $30$, o que não é igual a $k\cdot b=33$ neste caso).

Problemas relacionados

Cada instância do problema de correspondência numérica 3-dimensional é uma instância de tanto o Problema das 3 Partições, e o problema de correspondência 3-dimensional.

Prova de NP-Completo

A NP-completude do problema de 3-partição é afirmado por Garey e Johnson em "Computers and Intractability; A Guide to the Theory of NP-Completeness", que as referências a este problema com o código [ SP16 ]. Isto é feito por uma redução de correspondência 3-dimensional através de 4-partição. Para provar NP-completude da correspondente numérica 3-dimensional, a prova é semelhante, mas a redução de correspondência 3-dimensional através de 4-partição deve ser usado.