Contexte: Les est défini comme suit (La définition est tirée de la note de cours de Jeff: Conférence 29: NP-Hard Problems . Vous pouvez également reportez-vous à correspondance en 3 dimensions ):
Exact-3D- Correspondance: Étant donné un ensemble $ S $ et une collection de sous-ensembles à trois éléments de $ S $, appelés triples , existe-t-il une sous-collection de triplets disjoints qui couvrent exactement $ S $ ?
Le problème 3-Partition est défini comme (Il provient également de Cours 29: NP-Hard Problems . Vous pouvez également vous référer à problème à 3 partitions .):
Étant donné un ensemble $ S $ de $ 3n $ entiers, peut-il être partitionné en sous-ensembles disjoints de trois éléments $ n $, de sorte que tous les sous-ensembles aient exactement la même somme?
On sait que le problème 3-Partition peut être prouvé comme étant NP-complet en réduisant le NP-complete Exact-3D-Matching problème. Et la NP-exhaustivité du problème Exact-3D-Matching est prouvée en lui réduisant le problème 3SAT (les deux sont donnés dans le livre Ordinateurs et intractabilité: guide de la théorie de la NP-exhaustivité ).
Problème: Mon problème est:
Comment prouver lexhaustivité NP du
Exact-3D-Matchingproblème en y réduisant le3-Partitionproblème?
Je nai trouvé ni articles ni notes de cours à ce sujet.
Commentaires
Réponse
Je pense que cette réduction devrait fonctionner:
Étant donné une instance à 3 PARTITIONS: $ n $ entiers $ a_1, \ ldots, a_ {3n} $ et une somme cible $ B $; marquez chaque entier avec un identifiant unique $ \ hat {a_i} $; puis construisez une collection de sous-ensembles de 3 éléments $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ tel que $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ et $ i_1 \ neq i_2 \ neq i_3 $ (la collection a $ O (n ^ 3) $ éléments).
Loriginal Le problème 3-PARTITION a une solution si et seulement sil existe un EXACT-3D-MATCHING $ C_ {j_1}, \ ldots, C_ {j_n} $ qui couvre $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
Par exemple, étant donné $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ nous construisons: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ et la collection de sous-ensembles de 3 éléments:
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 } Une correspondance exacte en 3D est donnée par:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } qui identifie également de manière unique une solution valide pour le problème original à 3 PARTITIONS .
Commentaires
- Oui, cela fonctionne. Je nai pas réussi à marquer chaque $ a_i $ comme unique. Merci.
Exact-3D-Matchingà3-Partitionpeut être facilement trouvée (bien que la réduction elle-même ne soit pas facile) dans les manuels. Par conséquent, je demande la direction inverse. Je vais changer le titre et accepter votre réponse.