Pozadí: Exact-3D-Matching problém je definován následovně (definice je z Jeffovy přednášky: Přednáška 29: NP-Hard Problems . Můžete také viz trojrozměrná shoda ):
Exact-3D- Odpovídající: Vzhledem k množině $ S $ a kolekci tříprvkových podmnožin $ S $, zvaných triples , existuje dílčí kolekce disjunktních trojic, které přesně pokrývají $ S $ ?
Problém 3-Partition je definován jako (je také z Lecture 29: NP-Hard Problems . Můžete se také podívat na 3-partition problem .):
Vzhledem k množině celých čísel $ S $ ve výši 3 n $ $, lze ji rozdělit na $ n $ disjunktní tříprvkové podmnožiny, takže každá podmnožina má přesně stejný součet?
Je známo, že problém 3-Partition lze prokázat jako NP-úplný snížením NP-úplného Exact-3D-Matching problém. A NP úplnost problému Exact-3D-Matching je prokázána redukcí problému 3SAT (oba jsou uvedeny v knize Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti ).
Problém: Můj problém je:
Jak prokázat NP úplnost
Exact-3D-Matchingproblém snížením3-Partitionproblému na něj?
Nenašel jsem ani papíry, ani poznámky k přednášce.
Komentáře
Odpověď
Myslím, že toto snížení by mělo fungovat:
Vzhledem k třídílné instanci: $ n $ celá čísla $ a_1, \ ldots, a_ {3n} $ a cílová částka $ B $; označte každé celé číslo jedinečným identifikátorem $ \ hat {a_i} $; pak vytvořte kolekci 3-dílných podmnožin $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ tak, že $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ a $ i_1 \ neq i_2 \ neq i_3 $ (kolekce obsahuje prvky $ O (n ^ 3) $).
Originál Problém 3-PARTITION má řešení, pokud a pouze tehdy, pokud existuje PŘESNÉ-3D-VYROVNÁNÍ $ C_ {j_1}, \ ldots, C_ {j_n} $, které pokrývá $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
Například zadáno $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ we build: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ and the collection of 3-elements 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 } Exact-3D-MATCHING je dán:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } , který také jednoznačně identifikuje platné řešení pro původní 3-PARTITION problém .
Komentáře
- Ano, funguje to. Nepodařilo se mi označit každý $ a_i $ jedinečný. Díky.
Exact-3D-Matchingna3-Partitionlze snadno najít (i když samotná redukce není snadná) v učebnicích. Proto žádám o opačný směr. Změním název a přijmu vaši odpověď.