Baggrund: Exact-3D-Matching -problemet defineres som følger (Definitionen er fra Jeffs forelæsningsnotat: Forelæsning 29: NP-hårde problemer . Du kan også se 3-dimensionel matchning ):
Exact-3D- Matching: Givet et sæt $ S $ og en samling af tre-element-undergrupper på $ S $, kaldet triples , er der en under-samling af uensartede tredobler, der nøjagtigt dækker $ S $ ?
3-Partition problemet er defineret som (Det er også fra Forelæsning 29: NP-hårde problemer . Du kan også henvise til 3-partitionsproblem .):
Givet et sæt $ S $ på $ 3n $ heltal, kan det opdeles i $ n $ uensartede tre-element-undergrupper, således at hver delmængde har nøjagtig den samme sum? / p>
Det er kendt, at 3-Partition problemet kan bevises at være NP-komplet ved at reducere NP-komplet Exact-3D-Matching problem med det. Og NP-fuldstændigheden af Exact-3D-Matching problemet bevises ved at reducere 3SAT problemet til det (begge er angivet i bogen Computere og indtrængelighed: En guide til teorien om NP-fuldstændighed ).
Problem: Mit problem er:
Sådan bevises NP-fuldstændigheden af
Exact-3D-Matchingproblemet ved at reducere3-Partitionproblemet til det?
Jeg har hverken fundet papirer eller forelæsningsnotater om det.
Kommentarer
Svar
Jeg synes, at denne reduktion skal fungere:
Givet en 3-PARTITION instans: $ n $ heltal $ a_1, \ ldots, a_ {3n} $ og en målsum $ B $; marker hvert heltal med en unik identifikator $ \ hat {a_i} $; opbyg derefter en samling af 3-elementers undergrupper $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ sådan at $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ og $ i_1 \ neq i_2 \ neq i_3 $ (samlingen har $ O (n ^ 3) $ -elementer).
Originalen 3-DELT problem har en løsning, hvis og kun hvis der findes en EXACT-3D-MATCHING $ C_ {j_1}, \ ldots, C_ {j_n} $, der dækker $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
For eksempel givet $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ vi bygger: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ og samlingen af 3-elementundersæt:
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 gives af:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } der også entydigt identificerer en gyldig løsning til det originale 3-PARTITION problem .
Kommentarer
- Ja, det virker. Jeg kunne ikke markere hver $ a_i $ unik. Tak.
Exact-3D-Matchingtil3-Partitionkan let findes (selvom reduktionen i sig selv ikke er let) i lærebøger. Derfor beder jeg om den omvendte retning. Jeg ændrer titlen og accepterer dit svar.