Problema Hitting Set (HS) este definită după cum urmează. Fie $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ colecția subsetului S, adică $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Vrem să știm dacă există $ {S} „\ subset S $ unde $ | {S} „| < k $ astfel încât $ S_i \ cap S „\ neq \ emptyset $, $ i = 1,2, …, m. $
Dovediți că HS este Np-Complete.
Sugestie : Când $ | S_i | = 2 $, HS devine Vertex Cover, știe deja că este complet NP.
Comentarii
- Ce ai încercat? Unde ai făcut rămânem blocați? ' suntem bucuroși să vă ajutăm să înțelegeți conceptele, dar este puțin probabil să rezolvați exerciții pentru dvs. Este posibil să găsiți această pagină este utilă pentru îmbunătățirea întrebării dvs.
Răspuns
3SAT este redus la Hitting Setați problema. Având în vedere un 3SAT $ \ phi $ cu clauze $ m $ și variabile $ n $, definiți
$$ 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 \ în S \ text {și} (y_1 \ lor y_2 \ lor y_3) \ text {este o clauză.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {pentru toți variabilă} x. $$ $$ k = n $$
Să presupunem că $ \ phi $ este satisfăcătoare, atunci există o atribuire de valoare adevărată pentru variabilele $ n $. Deci, adăugați $ x $ la $ S „$ dacă $ x = adevărat $, altfel adăugați $ \ overline {x} $ la $ S” $.
Acum, presupuneți că problema HS are o soluție $ S „$. Apoi, deoarece pentru fiecare variabilă $ x $, $ S” \ cap S_x \ neq \ emptyset $, $ S „$ are cel puțin $ n $ literale de forma $ x $ sau $ \ overline {x} $ pentru fiecare variabilă $ x $. În plus, nu $ x $ și $ \ overline {x} $ pot aparține lui $ S „$ în același timp, deoarece dimensiunea $ S” $ este cel mult $ n $. De asemenea, pentru fiecare clauză $ C_i $, $ S „\ cap S_i \ neq \ emptyset $ și astfel pentru fiecare clauză selectăm $ y_i \ în S” \ cap S_i $ și setăm $ x = adevărat $ dacă $ y_i = x $ și $ x = false $ dacă $ y_i = \ overline {x} $.
Comentarii
- puteți afișa o instanță pozitivă și una negativă?
Răspuns
Este ușor să arăți că Hitting Set este în NP. O soluție trebuie doar să prezinte setul H – se poate verifica cu ușurință în timp polinomial dacă H are dimensiunea k și intersectează fiecare dintre mulțimile B1, …, Bm.
Reducem din acoperirea vârfului. Luați în considerare o instanță a vârfului problema de acoperire – graficul G = (V, E) și un întreg pozitiv k. O mapăm la o instanță a problemei setului de lovire după cum urmează. Mulțimea A este mulțimea vârfurilor V. Pentru fiecare muchie e ∈ E, avem un set Se format din cele două puncte finale ale lui e. Este ușor de văzut că un set de vârfuri S este un capac de vârf al lui G dacă elementele corespunzătoare formează un set de lovituri în instanța setului de lovituri.
Comentarii
- Bun venit la ComputerScience @ SE. Utilizare interesantă a simbolului special
∈– este obișnuit să folosiți MathJax, permițând, de exemplu, subscrierea corectă: $ B_1, \ dots, B_m $. - ce se întâmplă dacă dimensiunea Se este mai mare de 2? Va funcționa?
Răspuns
Problema setului de lovire este echivalentă cu problema acoperirii setului, care este definită după cum urmează:
INPUT: o colecție C de subseturi ale unui set finit S.
SOLUȚIE: Un set de acoperire pentru S, adică un subset $ C „\ subseteq C $ astfel că fiecare element din S aparține cel puțin unui membru din $ C „$.
Având în vedere $ k $ există o acoperire setată $ C” $ astfel încât $ \ vert C „\ vert \ leq k $?
Acest lucru pare a fi o temă, așa că vă las să vă dați seama cum, având în vedere o instanță a Set Cover, o puteți converti într-o instanță echivalentă a Hitting Set.
În caz contrar, dacă doriți să urmați indiciul, mai întâi arătați că Hitting Set în $ NP $, căruia i se oferă o soluție, îl puteți verifica în timp polinomial.
Apoi, arătați că dat un grafic $ G = (V, E) $, găsirea unui capac de vârf de dimensiunea $ k $ este echivalentă cu găsirea unui set de dimensiuni $ k $. Adică, dacă $ | E | = m $, puteți crea o instanță de set de lovituri cu aceeași cantitate de seturi.