A találati készlet problémát (HS) a következőképpen definiáljuk. Legyen $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ az S részhalmazának gyűjteménye, azaz $ S_i \ subseteq S, \ mind i $
- $ k \ in \ mathbb {N} $
Szeretnénk tudni, hogy létezik-e $ {S} “\ S S részhalmaz, ahol $ | {S} “| < k $ oly módon, hogy $ S_i \ cap S “\ neq \ emptyyset $, $ i = 1,2, …, m. $
Bizonyítsa be, hogy a HS Np-Complete.
Tipp : Amikor $ | S_i | = 2 $, a HS Vertex Cover lesz, már tudja, hogy NP-teljes.
Megjegyzések
- Mit próbáltál? Hol próbáltál elakad? Mi ' örömmel segítünk a fogalmak megértésében, de valószínűleg nem csak a gyakorlatok megoldása érheti el ezt. Találhatja ezt: ez az oldal hasznos a kérdésed fejlesztésében.
Válasz
A 3SAT az ütőre csökken Probléma beállítása. Adott egy 3SAT $ \ phi $, amelynek $ m $ záradékai és $ n $ változói vannak, definiálva
$$ 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 \ S \ text {és} (y_1 \ lor y_2 \ lor y_3) a \ text {egy záradék.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {for all változó} x. $$ $$ k = n $$
Tegyük fel, hogy a $ \ phi $ kielégítő, akkor a $ n $ változókhoz van igaz érték-hozzárendelés. Tehát adja hozzá a következőt: $ x $ a $ S “$ -hoz, ha $ x = true $, különben adja hozzá a $ \ overline {x} $ -t a $ S-hez.
Most tegyük fel, hogy a HS-problémának van megoldása $ S “$. Akkor mivel minden $ x $ változó esetén $ S” \ cap S_x \ neq \ emptyyset $, $ S “$ -nak legalább $ n $ literálja van a következő formában: $ x $ vagy $ \ overline {x} $ minden $ x $ változóhoz. Ezenkívül nem tartozhat $ x $ és $ \ overline {x} $ a $ S “$ -hoz, mivel a $ S” $ mérete legfeljebb $ n $. minden $ C_i $, $ S “\ cap S_i \ neq \ emptyyset $ záradékot, és így minden egyes záradékhoz kiválasztjuk az $ y_i \ -t az S” \ cap S_i $ -ban, és beállítjuk az $ x = true $ értéket, ha $ y_i = x $ és $ x = false $, ha $ y_i = \ overline {x} $.
Megjegyzések
- mutathat pozitív és negatív példányt?
Válasz
Könnyű kimutatni, hogy a Hitting Set NP-ben van. A megoldásnak csak ki kell mutatnia a H halmazt – polinomiális időben könnyen ellenőrizhető, hogy H értéke k-e és metszi-e a B1, …, Bm halmazok mindegyikét.
Csúszik a csúcsborításból. Tekintsük a csúcs példányát borító probléma – G = (V, E) gráf és pozitív k egész szám. Az ütési halmazprobléma egyik példájára térképezzük fel az alábbiak szerint. Az A halmaz az V csúcsok halmaza. Minden e ∈ E élre van egy Se szettünk, amely e két végpontból áll. Könnyen belátható, hogy az S csúcsok halmaza G csúcsborítója, ha a megfelelő elemek ütő halmazt alkotnak az ütő halmaz példányban.
Megjegyzések
- Üdvözli a ComputerScience @ SE. A
∈speciális szimbólum érdekes használata – gyakori a MathJax használata, amely lehetővé teszi például a megfelelő indexelést: $ B_1, \ dots, B_m $. - mi lenne, ha a Se mérete nagyobb, mint 2? Működni fog?
Válasz
Az ütőhalmaz-probléma egyenértékű a meghatározott a következőképpen:
INPUT: egy véges S halmaz C gyűjteménye.
MEGOLDÁS: Az S készlet halmazfedele, azaz egy $ C “\ subeteq C $ részhalmaz hogy az S minden eleme a $ C “$ legalább egy tagjához tartozik.
Adott $ k $ létezik-e olyan beállított fedél $ C” $, hogy $ \ vert C “\ vert \ leq k $?
Ez úgy néz ki, mint egy házi feladat, ezért hagyom, hogy kitalálja, hogyan lehet a Set Cover egy példányára való tekintettel átalakítani azt a Hitting Set megfelelő példányává.
Ellenkező esetben, ha követni szeretné a célzást, először megmutatja, hogy a Hitting Set in $ NP $, amely megoldást kap, azt ellenőrizheti polinomi időben.
Ezután megmutatja, hogy adott egy $ G grafikon = (V, E) $, a $ k $ méretű csúcsborító megtalálása egyenértékű a $ k $ méretű ütőhalmaz megtalálásával. Vagyis ha $ | E | = m $, akkor ugyanolyan halmazokkal készíthet ütő halmazpéldányt.