Bakgrund: Exact-3D-Matching -problem definieras enligt följande (Definitionen är från Jeff: s föreläsningsnot: Föreläsning 29: NP-hårda problem . Du kan också se 3-dimensionell matchning ):
Exact-3D- Matchande: Med tanke på en uppsättning $ S $ och en samling av treelement underuppsättningar på $ S $, kallad tripler , finns det en undersamling av ojämna tripplar som exakt täcker $ S $ ?
3-Partition problemet definieras som (Det är också från Föreläsning 29: NP-hårda problem . Du kan också hänvisa till 3-partition problem .):
Med en uppsättning $ S $ på $ 3n $ heltal, kan den delas upp i $ n $ separata treelementundersättningar, så att varje delmängd har exakt samma summa?
Det är känt att 3-Partition problemet kan bevisas vara NP-komplett genom att minska NP-komplett Exact-3D-Matching problem med det. Och NP-fullständigheten av Exact-3D-Matching problemet bevisas genom att reducera 3SAT problemet till det (båda anges i boken Datorer och intrakterbarhet: En guide till teorin om NP-fullständighet ).
Problem: Mitt problem är:
Hur man bevisar NP-fullständigheten av
Exact-3D-Matchingproblemet genom att minska3-Partitionproblemet till det?
Jag har varken hittat papper eller föreläsningsanteckningar om det.
Kommentarer
Svar
Jag tycker att denna minskning borde fungera:
Givet en 3-PARTITION-instans: $ n $ heltal $ a_1, \ ldots, a_ {3n} $ och en målsumma $ B $; markera varje heltal med en unik identifierare $ \ hat {a_i} $; bygg sedan en samling av 3-elementundersättningar $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ så att $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ och $ i_1 \ neq i_2 \ neq i_3 $ (samlingen har $ O (n ^ 3) $ element).
Originalet 3-PARTITION-problemet har en lösning om och endast om det finns en EXAKT-3D-MATCHING $ C_ {j_1}, \ ldots, C_ {j_n} $ som täcker $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
Till exempel ges $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ vi bygger: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ och samlingen av 3-element underuppsättningar:
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 } En Exact-3D-MATCHING ges av:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } som också unikt identifierar en giltig lösning för det ursprungliga 3-PARTITION-problemet .
Kommentarer
- Ja, det fungerar. Jag misslyckades med att markera varje $ a_i $ unik. Tack.
Exact-3D-Matchingtill3-Partitionkan lätt hittas (även om själva minskningen inte är lätt) i läroböcker. Därför ber jag omvänd riktning. Jag ändrar titeln och accepterar ditt svar.