Tło: Exact-3D-Matching jest zdefiniowany następująco (definicja pochodzi z notatki z wykładu Jeffa: Wykład 29: Problemy NP-trudne . Możesz również patrz trójwymiarowe dopasowanie ):
Exact-3D- Dopasowywanie: biorąc pod uwagę zbiór $ S $ i zbiór trzyelementowych podzbiorów $ S $, zwanych trójek , czy istnieje pod-zbiór rozłącznych trójek, który dokładnie pokrywa $ S $ ?
Problem 3-Partition jest zdefiniowany jako (pochodzi również z Wykład 29: NP-trudne problemy . Możesz również zapoznać się z tematem Problem z trzema partycjami .):
Biorąc pod uwagę zbiór $ S $ 3n $ liczb całkowitych, czy można go podzielić na $ n $ rozłączne podzbiory trzyelementowe, tak aby każdy podzestaw miał dokładnie taką samą sumę?
Wiadomo, że problem 3-Partition można wykazać jako NP-zupełny, zmniejszając wartość NP-ukończenia Exact-3D-Matching problem. A NP-kompletność problemu Exact-3D-Matching jest udowodniona poprzez zredukowanie do niego problemu 3SAT (oba są podane w książce Komputery i trudność: przewodnik po teorii NP-kompletności ).
Problem: Mój problem jest taki:
Jak udowodnić kompletność NP
Exact-3D-Matching, zmniejszając3-Partitionproblem?
Nie znalazłem ani dokumentów, ani notatki do wykładu na ten temat.
Komentarze
Odpowiedź
Myślę, że ta redukcja powinna zadziałać:
Biorąc pod uwagę instancję 3-PARTITION: $ n $ liczby całkowite $ a_1, \ ldots, a_ {3n} $ i suma docelowa $ B $; oznacz każdą liczbę całkowitą unikalnym identyfikatorem $ \ hat {a_i} $; następnie utwórz zbiór 3-elementowych podzbiorów $ 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 $ i $ i_1 \ neq i_2 \ neq i_3 $ (kolekcja zawiera $ O (n ^ 3) $ elementów).
Oryginał Problem 3-PARTYCJI ma rozwiązanie wtedy i tylko wtedy, gdy istnieje DOKŁADNE DOPASOWANIE 3D $ C_ {j_1}, \ ldots, C_ {j_n} $, które obejmuje $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
Na przykład biorąc pod uwagę $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ budujemy: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ i zbiór podzbiorów 3-elementowych:
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 } Dokładne dopasowanie 3D daje:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } , które również jednoznacznie identyfikuje poprawne rozwiązanie pierwotnego problemu 3-PARTYCJI .
Komentarze
- Tak, to działa. Nie udało mi się oznaczyć każdego $ a_i $ jako unikalnego. Dzięki.
Exact-3D-Matchingdo3-Partitionmożna łatwo znaleźć (chociaż sama redukcja nie jest łatwa) w podręcznikach. Dlatego proszę o odwrotny kierunek. Zmienię tytuł i zaakceptuję Twoją odpowiedź.