Histórico: O Exact-3D-Matching problema é definido como segue (a definição é da nota de aula de Jeff: Aula 29: Problemas NP-difíceis . Você também pode consulte correspondência tridimensional ):
Exact-3D- Correspondência: dado um conjunto $ S $ e uma coleção de subconjuntos de três elementos de $ S $, chamados de triplos , existe uma sub-coleção de triplos disjuntos que cobrem exatamente $ S $ ?
O 3-Partition problema é definido como (Também é de Aula 29: Problemas NP-difíceis . Você também pode consultar o problema de 3 partições .):
Dado um conjunto $ S $ de $ 3n $ inteiros, ele pode ser particionado em $ n $ subconjuntos de três elementos disjuntos, de modo que todos os subconjuntos tenham exatamente a mesma soma?
Sabe-se que o 3-Partition problema pode ser provado como NP-completo reduzindo o NP-completo Exact-3D-Matching problema para ele. E a integridade NP do Exact-3D-Matching problema é provada reduzindo o 3SAT problema a ele (ambos são fornecidos no livro Computadores e intratabilidade: um guia para a teoria da NP-completude ).
Problema: Meu problema é:
Como provar a integridade NP do
Exact-3D-Matchingproblema reduzindo o3-Partitionproblema a ele?
Não encontrei documentos nem notas de aula sobre ele.
Comentários
Resposta
Acho que essa redução deve funcionar:
Dada uma instância de 3 PARTIÇÕES: $ n $ inteiros $ a_1, \ ldots, a_ {3n} $ e uma soma alvo $ B $; marque cada inteiro com um identificador único $ \ hat {a_i} $; em seguida, construa uma coleção de subconjuntos de 3 elementos $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ de modo que $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ e $ i_1 \ neq i_2 \ neq i_3 $ (a coleção tem $ O (n ^ 3) $ elementos).
O original O problema de 3 PARTIÇÕES tem solução se e somente se existir um EXACT-3D-MATCHING $ C_ {j_1}, \ ldots, C_ {j_n} $ que cobre $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
Por exemplo, dado $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ nós construímos: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ e a coleção 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 } Um Exact-3D-MATCHING é fornecido por:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } que também identifica exclusivamente uma solução válida para o problema original de 3 PARTIÇÕES .
Comentários
- Sim, funciona. Não consegui marcar cada $ a_i $ como único. Obrigado.
Exact-3D-Matchingpara3-Partitionpode ser facilmente encontrada (embora a redução em si não seja fácil) em livros didáticos. Portanto, estou pedindo a direção inversa. Vou mudar o título e aceitar sua resposta.