Het Hitting Set Problem (HS) wordt als volgt gedefinieerd. Laat $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ verzameling van subset van S ie $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
We willen weten of $ {S} “\ subset S $ bestaat waar $ | {S} “| < k $ zodanig dat $ S_i \ cap S “\ neq \ emptyset $, $ i = 1,2, …, m. $
Bewijs dat HS Np-compleet is.
Hint : When $ | S_i | = 2 $, HS wordt Vertex Cover, weet al dat het NP-compleet is.
Opmerkingen
- Wat heb je geprobeerd? Waar heb je vastlopen? We ' helpen u graag de concepten te begrijpen, maar het is onwaarschijnlijk dat u dit kunt oplossen door oefeningen voor u op te lossen. Misschien vindt u deze pagina nuttig bij het verbeteren van uw vraag.
Answer
3SAT wordt gereduceerd tot de Hitting Stel een probleem in. Gegeven een 3SAT $ \ phi $ met $ m $ clausules en $ n $ variabelen, definieer
$$ 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 {en} (y_1 \ lor y_2 \ lor y_3) \ text {is een clausule.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {for all variabele} x. $$ $$ k = n $$
Veronderstel dat $ \ phi $ voldoet, dan is er een toewijzing van echte waarde voor $ n $ variabelen. Dus voeg $ x $ toe aan $ S “$ if $ x = true $, voeg anders $ \ overline {x} $ aan $ S” $ toe.
Stel nu dat het HS-probleem een oplossing heeft $ S “$. En aangezien voor elke variabele $ x $, $ S” \ cap S_x \ neq \ emptyset $, $ S “$ ten minste $ n $ literals heeft in de vorm $ x $ of $ \ overline {x} $ voor elke variabele $ x $. Bovendien mogen $ x $ en $ \ overline {x} $ niet tegelijkertijd tot $ S “$ behoren, aangezien de grootte van $ S” $ maximaal $ n $ is. Ook voor elke clausule $ C_i $, $ S “\ cap S_i \ neq \ emptyset $ en dus selecteren we voor elke clausule $ y_i \ in S” \ cap S_i $, en stellen $ x = true $ if $ y_i = x $ en $ x = false $ if $ y_i = \ overline {x} $.
Reacties
- kun je een positieve en een negatieve instantie laten zien?
Answer
Het is gemakkelijk aan te tonen dat Hitting Set zich in NP bevindt. Een oplossing hoeft alleen de set H te tonen – men kan gemakkelijk in polynomiale tijd verifiëren of H de grootte k heeft en elk van de sets B1,…, Bm doorsnijdt.
We verminderen vanaf hoekpuntdekking. Beschouw een instantie van het hoekpunt bedek probleem – grafiek G = (V, E) en een positief geheel getal k. We wijzen het als volgt toe aan een instantie van het probleem met het raken van sets. De set A is de set hoekpunten V. Voor elke rand e ∈ E hebben we een set Se bestaande uit de twee eindpunten van e. Het is gemakkelijk in te zien dat een set hoekpunten S een topdekking is van G als de corresponderende elementen een hitting set vormen in de hitting set instantie.
Comments
- Welkom bij ComputerScience @ SE. Interessant gebruik van het speciale symbool
∈– het is gebruikelijk om MathJax te gebruiken, waardoor bijvoorbeeld correct abonneren mogelijk is: $ B_1, \ dots, B_m $. - wat als grootte van Se is groter dan 2? Zal het werken?
Answer
Het Hitting Set-probleem is gelijk aan het Set Cover-probleem, dat is gedefinieerd als volgt:
INPUT: een verzameling C van subsets van een eindige set S.
OPLOSSING: Een set cover voor S, dwz een subset $ C “\ subseteq C $ dergelijke dat elk element in S toebehoort aan tenminste één lid van $ C “$.
Gegeven $ k $ bestaat het een set cover $ C” $ zodanig dat $ \ vert C “\ vert \ leq k $?
Dit ziet eruit als huiswerk, dus ik laat je uitzoeken hoe je, gegeven een instantie van Set Cover, het kunt converteren naar een gelijkwaardige instantie van Hitting Set.
Anders, als je wilt de hint volgen, je laat eerst zien dat Hitting Set in $ NP $ is, dat geeft een oplossing die je kunt verifiëren in polynomiale tijd.
Vervolgens laat je dat zien met een grafiek $ G = (V, E) $, het vinden van een hoekpuntbedekking van grootte $ k $ is gelijk aan het vinden van een treffende set van grootte $ k $. Dat wil zeggen, als $ | E | = m $, kunt u een hitting set-instantie bouwen met hetzelfde aantal sets.