Achtergrond: De Exact-3D-Matching probleem wordt als volgt gedefinieerd (de definitie komt uit Jeffs aantekening: Lezing 29: NP-moeilijke problemen . Je kunt ook verwijs naar 3-dimensionale matching ):
Exact-3D- Overeenstemming: Gegeven een set $ S $ en een verzameling van drie-element subsets van $ S $, genaamd triples , is er een sub-collectie van disjuncte triples die precies $ S $ dekken ?
Het 3-Partition probleem is gedefinieerd als (het is ook van Lezing 29: NP-moeilijke problemen . Je kunt ook verwijzen naar probleem met 3 partities .):
Gegeven een set $ S $ van $ 3n $ gehele getallen, kan deze dan worden onderverdeeld in $ n $ disjuncte subsets van drie elementen, zodat elke subset exact dezelfde som heeft?
Het is bekend dat kan worden aangetoond dat het probleem 3-Partition NP-compleet is door de NP-complete Exact-3D-Matching probleem. En de NP-volledigheid van het Exact-3D-Matching -probleem wordt bewezen door het 3SAT -probleem te verminderen (beide worden gegeven in het boek Computers en onhandelbaarheid: een gids voor de theorie van NP-volledigheid ).
Probleem: Mijn probleem is:
Hoe de NP-volledigheid van de probleem door het
3-Partitionprobleem te verkleinen?
Ik heb noch papers noch dictaten erover.
Opmerkingen
Antwoord
Ik denk dat deze reductie zou moeten werken:
Gegeven een 3-PARTITIE instantie: $ n $ gehele getallen $ a_1, \ ldots, a_ {3n} $ en een beoogde som $ B $; markeer elk geheel getal met een unieke identificatie $ \ hat {a_i} $; bouw vervolgens een verzameling van 3-elementen subsets $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ zodat $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ en $ i_1 \ neq i_2 \ neq i_3 $ (de collectie heeft $ O (n ^ 3) $ elementen).
Het origineel 3-PARTITIE probleem heeft een oplossing als en slechts als er een EXACT-3D-MATCHING $ C_ {j_1}, \ ldots, C_ {j_n} $ bestaat die $ S = \ hat {a} _ {1}, \ ldots dekt , \ hat {a} _ {3n} $.
Bijvoorbeeld $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ we bouwen: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ en de verzameling van 3-elementen subsets:
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 } Een Exact-3D-MATCHING wordt gegeven door:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } die ook op unieke wijze een geldige oplossing identificeert voor het oorspronkelijke 3-PARTITION-probleem .
Reacties
- Ja, het werkt. Ik heb niet elke $ a_i $ uniek gemarkeerd. Bedankt.
Exact-3D-Matchingnaar3-Partitionkan gemakkelijk worden gevonden (hoewel de reductie zelf niet eenvoudig is) in studieboeken. Daarom vraag ik om de omgekeerde richting. Ik zal de titel veranderen en je antwoord accepteren.