Tausta: Exact-3D-Matching -ongelma määritellään seuraavasti (Määritelmä on Jeffin luentomonisteesta: Luento 29: NP-kovat ongelmat . Voit myös viittaa kolmiulotteiseen vastaavuuteen ):
Exact-3D- Yhteensopivuus: Kun otetaan huomioon joukko $ S $ ja $ S $: n kolmiosainen osajoukko, nimeltään kolmikot , onko olemassa joukko epäyhtenäisiä kolmikoita, jotka kattavat tarkalleen $ S $ ?
3-Partition -ongelma määritellään seuraavasti: (Se on myös Luento 29: NP-kovat ongelmat . Voit myös viitata 3-osio-ongelmaan .):
Jos joukko $ S $ on $ 3n $ kokonaislukua, voidaanko se osioida $ n $ disjoint -elementteihin siten, että jokaisella osajoukolla on täsmälleen sama summa?
Tiedetään, että 3-Partition -ongelman voidaan osoittaa olevan NP-täydellinen vähentämällä NP-täydellinen Exact-3D-Matching ongelma. Ja ongelman Exact-3D-Matching NP-täydellisyys todistetaan vähentämällä 3SAT -ongelma siihen (molemmat on annettu kirjassa Tietokoneet ja haastavuus: Opas NP-täydellisyyden teoriaan ).
Ongelma: Minun ongelmani on:
Kuinka todistaa ongelma vähentämällä
3-Partition-ongelma siihen?
En ole löytänyt papereita eikä luentotiedot siitä.
Kommentit
Vastaa
Mielestäni tämän vähennyksen pitäisi toimia:
Annettu 3-OSALLINEN esiintymä: $ n $ kokonaislukua $ a_1, \ ldots, a_ {3n} $ ja tavoitesumma $ B $; merkitse kukin kokonaisluku yksilöllisellä tunnuksella $ \ hat {a_i} $; rakenna sitten kokoelma 3-elementtisiä alajoukkoja $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ siten, että $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ ja $ i_1 \ neq i_2 \ neq i_3 $ (kokoelmassa on elementtejä $ O (n ^ 3) $).
Alkuperäinen 3-OSALLISUUS-ongelmalla on ratkaisu vain ja vain, jos on olemassa TARKKA 3D-VASTAAVA $ C_ {j_1}, \ ldots, C_ {j_n} $, joka peittää $ S = \ hat {a} _ {1}, \ ldots , \ hat {a} _ {3n} $.
Esimerkiksi annettu $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 Rakennamme $: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ ja 3-osaisten alijoukkojen kokoelma:
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 } Tarkka 3D-MATCHING antaa:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } joka myös yksilöi kelvollisen ratkaisun alkuperäiselle 3-OSALLISUUS-ongelmalle .
Kommentit
- Kyllä, se toimii. Kukin $ a_i $ ei merkitty yksilölliseksi. Kiitos.
Exact-3D-Matchingmuotoon3-Partitionlöytyy helposti (vaikka itse pienentäminen ei ole helppoa) oppikirjoista. Siksi pyydän päinvastaista suuntaa. Muutan otsikkoa ja hyväksyn vastauksesi.