Bakgrunn: Exact-3D-Matching problemet defineres som følger (Definisjonen er fra Jeffs forelesningsnotat: Forelesning 29: NP-harde problemer . Du kan også referer til 3-dimensjonal matching ):
Exact-3D- Matching: Gitt et sett $ S $ og en samling med tre-element-undergrupper på $ S $, kalt triples , er det en undersamling av usammenhengende tripler som dekker $ S $ ?
3-Partition problemet er definert som (Det er også fra Forelesning 29: NP-harde problemer . Du kan også referere til 3-partisjon problem .):
Gitt et sett $ S $ på $ 3n $ heltall, kan det deles inn i $ n $ uensartede tre-element-undergrupper, slik at hvert delmengde har nøyaktig samme sum?
Det er kjent at 3-Partition problemet kan bevises å være NP-komplett ved å redusere NP-komplett Exact-3D-Matching problem med det. Og NP-fullstendigheten av Exact-3D-Matching problemet bevises ved å redusere 3SAT problemet til det (begge er gitt i boka Datamaskiner og intraherbarhet: En guide til teorien om NP-fullstendighet ).
Problem: Problemet mitt er:
Hvordan bevise NP-fullstendigheten av
Exact-3D-Matchingproblemet ved å redusere3-Partitionproblemet til det?
Jeg har verken funnet papirer eller forelesningsnotater om det.
Kommentarer
Svar
Jeg synes denne reduksjonen skal fungere:
Gitt en 3-PARTITION forekomst: $ n $ heltall $ a_1, \ ldots, a_ {3n} $ og en målt sum $ B $; merke hvert heltall med en unik identifikator $ \ hat {a_i} $; Bygg deretter en samling med 3-elementers undergrupper $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ slik 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 bare hvis det eksisterer en EXACT-3D-MATCHING $ C_ {j_1}, \ ldots, C_ {j_n} $ som dekker $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
For eksempel gitt $ 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 av 3-elementundersett:
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 er gitt av:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } som også unikt identifiserer en gyldig løsning for det opprinnelige 3-PARTITION-problemet .
Kommentarer
- Ja, det fungerer. Jeg klarte ikke å merke hver $ a_i $ unik. Takk.
Exact-3D-Matchingtil3-Partitionkan lett bli funnet (selv om selve reduksjonen ikke er lett) i lærebøker. Derfor ber jeg om motsatt retning. Jeg vil endre tittelen og godta svaret ditt.