Hitting Set Problem (HS) er definert som følger. La $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ samling av delmengde av S dvs. $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Vi vil vite om det finnes $ {S} «\ delmengde S $ hvor $ | {S} «| < k $ slik at $ S_i \ cap S «\ neq \ emptyset $, $ i = 1,2, …, m. $
Bevis at HS er Np-Complete.
Hint : Når $ | S_i | = 2 $, HS blir Vertex Cover, vet allerede å være NP-komplett.
Kommentarer
- Hva prøvde du? Hvor gjorde du setter deg fast? Vi ' hjelper deg gjerne med å forstå konseptene, men det er lite sannsynlig at det bare er å løse øvelser for deg. Du finner denne siden er nyttig for å forbedre spørsmålet ditt.
Svar
3SAT er redusert til treffet Angi problem. Gitt en 3SAT $ \ phi $ med $ m $ klausuler og $ n $ variabler, definer
$$ 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 \ in S \ text {and} (y_1 \ lor y_2 \ lor y_3) \ text {er en klausul.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {for alle variabel} x. $$ $$ $$ k = n $$
Anta at $ \ phi $ er tilfredsstillende, så er det en virkelig verdi-tildeling for $ n $ -variabler. Så legg til $ x $ til $ S «$ hvis $ x = true $, ellers legg til $ \ overline {x} $ til $ S» $.
Anta nå at HS-problemet har en løsning $ S «$. Siden siden for hver variabel $ x $, $ S» \ cap S_x \ neq \ emptyset $, har $ S «$ minst $ n $ bokstav i form av $ x $ eller $ \ overline {x} $ for hver variabel $ x $. Videre kan ingen $ x $ og $ \ overline {x} $ tilhøre $ S «$ samtidig, siden størrelsen på $ S» $ maksimalt er $ n $. Også for hver ledd $ C_i $, $ S «\ cap S_i \ neq \ emptyset $ og så for hver ledd velger vi $ y_i \ i S» \ cap S_i $, og setter $ x = true $ hvis $ y_i = x $ og $ x = false $ hvis $ y_i = \ overline {x} $.
Kommentarer
- kan du vise en positiv og en negativ forekomst?
Svar
Det er lett å vise at Hitting Set er i NP. En løsning trenger bare å stille ut settet H – man kan enkelt verifisere i polynomisk tid om H er av størrelse k og krysser hvert av settene B1, …, Bm.
Vi reduserer fra toppdeksel. Tenk på en forekomst av toppunkt dekkproblem – graf G = (V, E) og et positivt heltall k. Vi tilordner det til en forekomst av treffsettet-problemet som følger. Settet A er settet med hjørner V. For hver kant e ∈ E har vi et sett Se som består av de to endepunktene til e. Det er lett å se at et sett med hjørner S er et toppdeksel på G, hvis de tilsvarende elementene danner et treffsett i treffsettet.
Kommentarer
- Velkommen til ComputerScience @ SE. Interessant bruk av spesialsymbol
∈– det er vanlig å bruke MathJax, slik at f.eks. Riktig abonnement: $ B_1, \ dots, B_m $. - hva om størrelsen på Se er større enn 2? Vil det fungere?
Svar
Hitting Set Problemet tilsvarer Set Cover Problem, det er definert som følger:
INNGANG: en samling C av delmengder av et endelig sett S.
LØSNING: Et settdeksel for S, dvs. en delmengde $ C «\ subseteq C $ slik at hvert element i S tilhører minst ett medlem av $ C «$.
Gitt $ k $ eksisterer det et sett dekker $ C» $ slik at $ \ vert C «\ vert \ leq k $?
Dette ser ut som et lekser, så jeg lar deg finne ut hvordan, gitt en forekomst av Set Cover kan du konvertere det til en tilsvarende forekomst av Hitting Set.
Ellers hvis du vil følge hintet, du viser først at Hitting Set in i $ NP $, som er gitt en løsning du kan bekrefte det i polynomial tid.
Deretter viser du at gitt en graf $ G = (V, E) $, å finne et toppdeksel på størrelse $ k $ tilsvarer å finne et treffende sett med størrelse $ k $. Det vil si at hvis $ | E | = m $, kan du bygge en treffende settforekomst med samme mengde sett.