Problém sady bití (HS) je definován následovně. Nechť $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ kolekce podmnožiny S tj. $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Chceme vědět, jestli existuje $ {S} „\ podmnožina S $ kde $ | {S} „| < k $ takové, že $ S_i \ cap S „\ neq \ emptyset $, $ i = 1,2, …, m. $
Dokažte, že HS je Np-Complete.
Nápověda : Když $ | S_i | = 2 $, HS se stává Vertex Cover, již vím, že je NP-kompletní.
Komentáře
- Co jste vyzkoušeli? Kde jste uvíznete? Jsme ' rádi, že vám pomůžeme porozumět konceptům, ale je nepravděpodobné, že by to bylo jen pomocí řešení cvičení. tato stránka užitečná při vylepšování vaší otázky.
Odpověď
3SAT se redukuje na Hitting Nastavit problém. Vzhledem k tomu, že 3SAT $ \ phi $ má klauzule $ m $ a proměnné $ n $, definujte
$$ 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 \ v S \ text {a} (y_1 \ lor y_2 \ lor y_3) \ text {je klauzule.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {pro všechny proměnná} x. $$ $$ k = n $$
Předpokládejme, že $ \ phi $ je uspokojivé, pak existuje přiřazení skutečné hodnoty pro proměnné $ n $. Přidejte tedy $ x $ do $ S „$ if $ x = true $, jinak přidejte $ \ overline {x} $ do $ S“ $.
Předpokládejme, že problém HS má řešení $ S „$. Potom, protože pro každou proměnnou $ x $, $ S“ \ cap S_x \ neq \ emptyset $, $ S „$ má alespoň $ n $ literály ve tvaru $ x $ nebo $ \ overline {x} $ pro každou proměnnou $ x $. Navíc žádné $ x $ a $ \ overline {x} $ nemusí patřit současně $ S „$, protože velikost $ S“ $ je maximálně $ n $. Také pro každá klauzule $ C_i $, $ S „\ cap S_i \ neq \ emptyset $ a tak pro každou klauzuli vybereme $ y_i \ v S“ \ cap S_i $ a nastavíme $ x = true $, pokud $ y_i = x $ a $ x = false $ if $ y_i = \ overline {x} $.
Komentáře
- můžete ukázat pozitivní a negativní instanci?
Odpověď
Je snadné ukázat, že Hitting Set je v NP. Řešení potřebuje pouze vystavit množinu H – lze snadno ověřit v polynomiálním čase, zda H má velikost k a protíná každou ze sad B1, …, Bm.
Redukujeme z vrcholového krytu. Zvažte instanci vrcholu problém obálky – graf G = (V, E) a kladné celé číslo k. Mapujeme to na instanci problému s úderovou sadou následujícím způsobem. Sada A je množina vrcholů V. Pro každou hranu e ∈ E máme množinu Se skládající se ze dvou koncových bodů e. Je snadné vidět, že sada vrcholů S je vrcholovým krytem G, pokud odpovídající prvky tvoří úderovou sadu v instanci úderové sady.
Komentáře
- Vítejte v ComputerScience @ SE. Zajímavé použití speciálního symbolu
∈– běžně se používá MathJax, který umožňuje např. Správné indexování: $ B_1, \ dots, B_m $. - co když velikost Se je větší než 2? Bude to fungovat?
Odpovědět
Problém zasažení sady je ekvivalentní problému Set Cover Problem, který je definován následovně:
INPUT: kolekce C podmnožin konečné množiny S.
ŘEŠENÍ: Sada krytí pro S, tj. podmnožinu $ C „\ subseteq C $ jako že každý prvek v S patří alespoň jednomu členovi $ C „$.
Vzhledem k $ k $ existuje sada krytů $ C“ $ tak, že $ \ vert C „\ vert \ leq k $?
Vypadá to jako domácí úkol, takže vás nechám přijít na to, jak jej vzhledem k instanci Set Cover můžete převést na ekvivalentní instanci Hitting Set.
Jinak, pokud chcete-li následovat nápovědu, nejprve ukážete, že Hitting Set in in $ NP $, které dostane řešení, které si můžete ověřit v polynomiálním čase.
Potom ukážete, že daný graf $ G = (V, E) $, nalezení vrcholového krytu velikosti $ k $ je ekvivalentní nalezení úderové sady velikosti $ k $. To znamená, že pokud $ | E | = m $, můžete vytvořit instanci sady bitů se stejným množstvím sad.