Lyöntijoukko-ongelma (HS) määritellään seuraavasti. Olkoon $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ kokoelma S: n osajoukko eli $ S_i \ subseteq S, \ kaikki i $
- $ k \ sisään \ mathbb {N} $
Haluamme tietää, onko $ {S} ”\ osajoukko S $ missä $ | {S} ”| < k $ siten, että $ S_i \ cap S ”\ neq \ emptyyset $, $ i = 1,2, …, m. $
Osoita, että HS on Np-täydellinen.
Vihje : Kun $ | S_i | = 2 $, HS: stä tulee Vertex Cover, tiedät jo olevan NP-täydellinen.
Kommentit
- Mitä yritit? Missä yritit juuttua jumiin? Olemme ' mielellään auttaneet ymmärtämään käsitteitä, mutta pelkkä harjoitusten ratkaiseminen ei todennäköisesti onnistu saavuttamaan sitä. Saatat löytää tämä sivu on hyödyllinen kysymyksesi parantamisessa.
Vastaus
3SAT on vähennetty osuvaksi Aseta ongelma. Kun 3SAT $ \ phi $ sisältää $ m $ -lausekkeet ja $ n $ -muuttujat, määritä
$$ S = \ {x_1, \ dots x_n, \ overline {x_1}, \ dots, \ overline {x_n} \} $$ $$ S_i = \ {y_1, y_2, y_3 \}, \ text {if} y_1, y_2, y_3 \ S \ text {ja} (y_1 \ lor y_2 \ lor y_3) \ text {on lauseke.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {kaikille muuttuja x. Lisää siis $ x $ kohtaan $ S ”$, jos $ x = true $, muuten lisää $ \ overline {x} $ kohtaan $ S”.
Oletetaan, että HS-ongelmassa on ratkaisu $ S ”$. Sitten koska jokaiselle muuttujalle $ x $, $ S” \ cap S_x \ neq \ emptyyset $, $ S ”$: lla on vähintään $ n $ literaalia muodossa $ x $ tai $ \ overline {x} $ jokaiselle muuttujalle $ x $. Lisäksi mikään $ x $ ja $ \ overline {x} $ eivät välttämättä kuulu $ S ”$: een samanaikaisesti, koska $ S” $ -koko on korkeintaan $ n $. kukin lauseke $ C_i $, $ S ”\ cap S_i \ neq \ emptyyset $ ja niin jokaiselle lausekkeelle valitaan $ y_i \ S: ssä” cap S_i $ ja asetetaan $ x = true $, jos $ y_i = x $ ja $ x = false $ jos $ y_i = \ yliviivat {x} $.
Kommentit
- voitko näyttää positiivisen ja negatiivisen esiintymän?
vastaus
On helppo osoittaa, että lyöntisarja on NP: ssä. Ratkaisun täytyy vain näyttää joukko H – Polynomiajassa voidaan helposti tarkistaa, onko H kooltaan k ja leikkaa kaikki joukot B1, …, Bm.
Pienennämme kärkipinnasta. Tarkastellaan kärkipisteen esiintymää kansiongelma – käyrä G = (V, E) ja positiivinen kokonaisluku k. Kartoitamme sen lyömäjoukon ongelmaan seuraavasti. Joukko A on joukko pisteitä V. Jokaiselle reunalle e ∈ E on joukko Se, joka koostuu e: n kahdesta päätepisteestä. On helppo nähdä, että joukko kärkipisteitä S on pisteiden peite Gffistä, kun vastaavat elementit muodostavat osumajoukon lyömäjoukko-ilmentymässä. >
∈ käyttö – on yleistä käyttää MathJaxia, mikä sallii esimerkiksi oikean alaindeksin: $ B_1, \ pisteet, B_m $. Vastaus
Lyömäjoukko-ongelma vastaa määriteltyä joukon kansion ongelmaa seuraavasti:
INPUT: joukko C rajallisen joukon S. alajoukoista.
RATKAISU: Joukon S joukko, eli osajoukko $ C ”\ subseteq C $ että jokainen elementti S: ssä kuuluu vähintään yhteen $ C ”$: n jäseneen.
Kun otetaan huomioon $ k $, onko olemassa joukko kansi $ C” $, että $ \ vert C ”\ vert \ leq k $?
Tämä näyttää kotitehtävältä, joten annan sinun selvittää, kuinka Set Cover Cover -esimerkillä voit muuntaa sen vastaavaksi Hitting Set -esimerkiksi.
Muussa tapauksessa, jos haluat seurata vihjettä, osoitat ensin, että lyönti asetetaan sisään $ NP $, jolle annetaan ratkaisu, voit tarkistaa sen polynomi-ajalla.
Sitten näytät, että annettu kaavio $ G = (V, E) $, koon $ k $ kärjessä olevan kärkikannen löytäminen vastaa lyöntijoukon koon $ k $ löytämistä. Toisin sanoen, jos $ | E | = m $, voit rakentaa osuvan joukon esiintymän samalla määrällä joukkoja.