Sfondo: Exact-3D-Matching il problema è definito come segue (la definizione è tratta dalla nota della lezione di Jeff: Lezione 29: Problemi NP-Difficili . Puoi anche fare riferimento a corrispondenza tridimensionale ):
Exact-3D- Corrispondenza: dato un insieme $ S $ e una raccolta di sottoinsiemi di tre elementi di $ S $, chiamati triple , esiste una sotto-raccolta di triple disgiunte che coprono esattamente $ S $ ?
Il problema 3-Partition è definito come (Deriva anche da Lezione 29: problemi NP-Hard . Puoi anche fare riferimento a problema a 3 partizioni .):
Dato un insieme $ S $ di $ 3n $ interi, può essere partizionato in $ n $ sottoinsiemi di tre elementi disgiunti, in modo che ogni sottoinsieme abbia esattamente la stessa somma?
È noto che il problema 3-Partition può essere dimostrato essere NP-completo riducendo il NP-completo Exact-3D-Matching problema ad esso. E la completezza NP del problema Exact-3D-Matching è dimostrata riducendo il problema 3SAT (entrambi sono riportati nel libro Computer e intrattabilità: una guida alla teoria della completezza NP ).
Problema: Il mio problema è:
Come dimostrare la NP-completezza del
Exact-3D-Matchingproblema riducendo il problema3-Partition?
Non ho trovato né documenti né note di lezione su di esso.
Commenti
Risposta
Penso che questa riduzione dovrebbe funzionare:
Data unistanza 3-PARTITION: $ n $ interi $ a_1, \ ldots, a_ {3n} $ e una somma target $ B $; contrassegna ogni numero intero con un identificatore univoco $ \ hat {a_i} $; quindi crea una raccolta di sottoinsiemi di 3 elementi $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ in modo tale che $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ e $ i_1 \ neq i_2 \ neq i_3 $ (la raccolta ha $ O (n ^ 3) $ elementi).
Loriginale Il problema a 3 PARTIZIONI ha una soluzione se e solo se esiste una CORRISPONDENZA ESATTA 3D $ C_ {j_1}, \ ldots, C_ {j_n} $ che copre $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
Ad esempio, dato $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ costruiamo: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ e la raccolta di sottoinsiemi di 3 elementi:
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 } Un CORRISPONDENZA 3D esatta è dato da:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } che identifica anche in modo univoco una soluzione valida per il problema delle 3 PARTIZIONI originale .
Commenti
- Sì, funziona. Non sono riuscito a contrassegnare ogni $ a_i $ come unico. Grazie.
Exact-3D-Matchinga3-Partitionpuò essere facilmente trovata (sebbene la riduzione stessa non sia facile) nei libri di testo. Pertanto, chiedo la direzione opposta. Cambierò il titolo e accetterò la tua risposta.