Fundal: Exact-3D-Matching Problema este definită după cum urmează (definiția provine din nota de curs a lui Jeff: Lectura 29: Probleme NP-Hard . De asemenea, puteți consultați potrivire tridimensională ):
Exact-3D- Potrivire: Având în vedere un set $ S $ și o colecție de subseturi de trei elemente de $ S $, numite tripluri , există o sub-colecție de tripluri disjuncte care acoperă exact $ S $ ?
Problema 3-Partition este definită ca (Este, de asemenea, din Prelegerea 29: Probleme NP-Hard . De asemenea, puteți consulta problema cu 3 partiții .):
Având în vedere un set $ S $ de $ 3n $ întregi, poate fi partiționat în $ n $ subseturi de trei elemente disjuncte, astfel încât fiecare subset să aibă exact aceeași sumă?
Se știe că problema 3-Partition se poate dovedi a fi NP-completă prin reducerea NP-completă Exact-3D-Matching problemă. Și NP-completitudinea problemei Exact-3D-Matching este dovedită prin reducerea problemei 3SAT la aceasta (ambele sunt date în cartea Computers and Intractability: A Guide to Theory of NP-Completeness ).
Problemă: Problema mea este:
Cum se dovedește completitudinea NP a
Exact-3D-Matchingproblemă reducând3-Partitionproblema la ea?
Nu am găsit nici hârtii, nici note de curs despre el.
Comentarii
Răspuns
Cred că această reducere ar trebui să funcționeze:
Având în vedere o instanță cu 3 PARTIȚII: $ n $ întregi $ a_1, \ ldots, a_ {3n} $ și o sumă țintă $ B $; marcați fiecare număr întreg cu un identificator unic $ \ hat {a_i} $; apoi construiți o colecție de subseturi de 3 elemente $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ astfel încât $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ și $ i_1 \ neq i_2 \ neq i_3 $ (colecția are $ O (n ^ 3) $ elemente).
Originalul Problema cu 3-PARTIȚII are o soluție dacă și numai dacă există un EXACT-3D-MATCHING $ C_ {j_1}, \ ldots, C_ {j_n} $ care acoperă $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
De exemplu, dat $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ construim: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ și colecția de subseturi cu 3 elemente:
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 } Un Exact-3D-MATCHING este dat de:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } care, de asemenea, identifică în mod unic o soluție validă pentru problema originală cu 3 PARTIȚII .
Comentarii
- Da, funcționează. Nu am reușit să marchez fiecare $ a_i $ unic. Mulțumesc.
Exact-3D-Matchingla3-Partitionpoate fi găsită cu ușurință (deși reducerea în sine nu este ușoară) în manuale. Prin urmare, cer direcția inversă. Voi schimba titlul și voi accepta răspunsul dvs.