Háttér: A Exact-3D-Matching probléma a következőképpen definiálható (A meghatározás Jeff előadásjegyzetéből származik: 29. előadás: NP-nehéz problémák . lásd: 3-dimenziós egyezés ):
Exact-3D- Egyezés: Adott egy $ S $ halmaz és a $ S $ háromelemes részhalmaza, az úgynevezett hármasok , létezik-e a disszjunkt hármasok részgyűjteménye, amely pontosan fedezi a $ S $ -t ?
A 3-Partition problémát a következők határozzák meg: (Ez is származik 29. előadás: NP-nehéz problémák . Hivatkozhat a 3-partíciós problémára .):
Ha egy $ S $ $ 3n $ egész számot megadunk, akkor felosztható-e $ n $ disjoint háromelemes részhalmazokra úgy, hogy minden részhalmaznak pontosan ugyanaz az összege?
Ismert, hogy a 3-Partition probléma NP-teljesnek bizonyítható az NP-teljes Exact-3D-Matching probléma. A Exact-3D-Matching probléma NP-teljességét pedig a 3SAT probléma csökkentésével bizonyítja (mindkettő meg van adva a Számítógépek és megoldhatatlanság: Útmutató az NP-teljesség elméletéhez ).
Probléma: A problémám a következő:
Hogyan igazolhatom a probléma a
3-Partitionprobléma csökkentésével?
Nem találtam sem papírt, sem előadásjegyzetek róla.
Hozzászólások
Válasz
Úgy gondolom, hogy ennek a csökkentésnek működnie kell:
Adott egy 3-PARTITION példány: $ n $ egész $ a_1, \ ldots, a_ {3n} $ és egy célösszeg $ B $; jelöljön meg minden egész számot egyedi azonosítóval $ \ hat {a_i} $; majd készítsen egy 3 elemű részhalmazot: $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ oly módon, hogy $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ és $ i_1 \ neq i_2 \ neq i_3 $ (a gyűjtemény $ O (n ^ 3) $ elemet tartalmaz).
Az eredeti A 3-PARTITION problémának akkor és csak akkor van megoldása, ha létezik PONTOS 3D-SEGÍTŐ $ C_ {j_1}, \ ldots, C_ {j_n} $, amely lefedi a $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
Például adott $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ építjük: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ és a 3 elemű részhalmazok gyűjteménye:
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 } Pontos 3D-MATCHING-et ad:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } amely egyedülállóan azonosítja az eredeti megoldást az eredeti 3-PARTITION problémára .
Megjegyzések
- Igen, működik. Nem sikerült minden egyes $ a_i $ -t egyedinek jelölnöm. Köszönöm.
Exact-3D-Matching-ről3-Partition-re könnyen megtalálható (bár maga a csökkentés nem könnyű) a tankönyvekben. Ezért a fordított irányt kérem. Megváltoztatom a címet, és elfogadom válaszát.