Hitting Set Problem (HS) er defineret som følger. Lad $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ samling af delmængde af S dvs. $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Vi vil gerne vide, om der findes $ {S} “\ subset S $ hvor $ | {S} “| < k $ sådan at $ S_i \ cap S “\ neq \ emptyset $, $ i = 1,2, …, m. $
Bevis, at HS er Np-komplet.
Tip : Når $ | S_i | = 2 $, HS bliver Vertex Cover, ved allerede at være NP-komplet.
Kommentarer
- Hvad prøvede du? Hvor har du sidder fast? Vi ' hjælper dig gerne med at forstå begreberne, men det er usandsynligt, at det kun er at løse øvelser for dig. Du finder muligvis denne side hjælper med at forbedre dit spørgsmål.
Svar
3SAT er reduceret til rammerne Angiv problem. Med 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 \ i 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 $$
Antag, at $ \ phi $ er tilfredsstillende, så er der en sandværditildeling for $ n $ -variabler. Så tilføj $ x $ til $ S “$ hvis $ x = sand $, ellers tilføj $ \ overline {x} $ til $ S” $.
Antag nu, at HS-problemet har en løsning $ S “$. Siden da for hver variabel $ x $, $ S” \ cap S_x \ neq \ emptyset $, har $ S “$ mindst $ n $ bogstaver i formen $ x $ eller $ \ overline {x} $ for hver variabel $ x $. Desuden kan ingen $ x $ og $ \ overline {x} $ tilhøre $ S “$ på samme tid, da størrelsen på $ S” $ højst er $ n $. Også for hver klausul $ C_i $, $ S “\ cap S_i \ neq \ emptyset $ og så for hver klausul vælger vi $ y_i \ i S” \ cap S_i $, og indstiller $ 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 let at vise, at Hitting Set er i NP. En løsning skal bare udstille sæt H – man kan let kontrollere i polynomial tid, om H er af størrelse k og skærer hvert af sætene B1, …, Bm.
Vi reducerer fra topdækslet. Overvej en forekomst af toppunktet dækproblem – graf G = (V, E) og et positivt heltal k. Vi kortlægger det til en forekomst af rammesætteproblemet som følger. Sættet A er sættet med hjørner V. For hver kant e ∈ E har vi et sæt Se, der består af de to slutpunkter for e. Det er let at se, at et sæt hjørner S er et hjørneomslag på G iff de tilsvarende elementer danner et rammesæt i den rammende sætforekomst.
Kommentarer
- Velkommen til ComputerScience @ SE. Interessant brug af specielt symbol
∈– det er almindeligt at bruge MathJax, hvilket f.eks. Tillader korrekt abonnement: $ B_1, \ dots, B_m $. - hvad hvis størrelse på Se er større end 2? Fungerer det?
Svar
Problemet med rammesættet svarer til problemet med sætomslag, der er defineret som følger:
INPUT: en samling C af delmængder af et endeligt sæt S.
LØSNING: Et sæt cover til S, dvs. en delmængde $ C “\ subseteq C $ sådan at hvert element i S tilhører mindst et medlem af $ C “$.
Givet $ k $ findes der et sæt cover $ C” $ sådan at $ \ vert C “\ vert \ leq k $?
Dette ligner et hjemmearbejde, så jeg lader dig finde ud af, hvordan du, givet en forekomst af Set Cover, kan konvertere det til en tilsvarende forekomst af Hitting Set.
Ellers hvis du vil følge hintet, du viser først, at Hitting Set in i $ NP $, der er givet en løsning, du kan verificere det i polynomisk tid.
Derefter viser du, at givet en graf $ G = (V, E) $, at finde et topdæksel i størrelse $ k $ svarer til at finde et slående sæt med størrelse $ k $. Det vil sige, at hvis $ | E | = m $, kan du oprette en hit-set-instans med det samme antal sæt.