Le problème de lensemble de frappe (HS) est défini comme suit. Soit $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ collection de sous-ensemble de S ie $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Nous voulons savoir sil existe $ {S} « \ subset S $ où $ | {S} « | < k $ tel que $ S_i \ cap S « \ neq \ emptyset $, $ i = 1,2, …, m. $
Prouvez que HS est Np-Complete.
Indice : Quand $ | S_i | = 2 $, HS devient Vertex Cover, déjà connu pour être NP-complete.
Commentaires
- Quavez-vous essayé? Où avez-vous Nous sommes ' heureux de vous aider à comprendre les concepts, mais il est peu probable que la résolution d’exercices pour vous y parvienne. Vous trouverez peut-être cette page utile pour améliorer votre question.
Réponse
3SAT est réduit à la frappe Définir le problème. Étant donné un 3SAT $ \ phi $ ayant des clauses $ m $ et des variables $ n $, définissez
$$ 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 {et} (y_1 \ lor y_2 \ lor y_3) \ text {est une clause.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {pour tous variable} x. $$ $$ k = n $$
Supposons que $ \ phi $ est satisfaisable, alors il y a une affectation de valeur vraie pour les variables $ n $. Donc, ajoutez $ x $ à $ S « $ if $ x = true $, sinon ajoutez $ \ overline {x} $ à $ S » $.
Maintenant, supposons que le problème HS a une solution $ S « $. Alors puisque pour chaque variable $ x $, $ S » \ cap S_x \ neq \ emptyset $, $ S « $ a au moins $ n $ littéraux de la forme $ x $ ou $ \ overline {x} $ pour chaque variable $ x $. De plus, aucun $ x $ et $ \ overline {x} $ ne peuvent appartenir à $ S « $ en même temps puisque la taille de $ S » $ est au plus de $ n $. Aussi, pour chaque clause $ C_i $, $ S « \ cap S_i \ neq \ emptyset $ et donc pour chaque clause nous sélectionnons $ y_i \ in S » \ cap S_i $, et définissons $ x = true $ si $ y_i = x $ et $ x = false $ if $ y_i = \ overline {x} $.
Commentaires
- pouvez-vous afficher une instance positive et une instance négative?
Réponse
Il est facile de montrer que Hitting Set est dans NP. Une solution a juste besoin dexposer lensemble H – on peut facilement vérifier en temps polynomial si H est de taille k et intersecte chacun des ensembles B1,…, Bm.
Nous réduisons à partir de la couverture de sommet. Considérons une instance du sommet problème de couverture – graphe G = (V, E) et un entier positif k. Nous le mappons à une instance du problème densemble de frappe comme suit. Lensemble A est lensemble des sommets V. Pour chaque arête e ∈ E, nous avons un ensemble Se constitué des deux extrémités de e. Il est facile de voir quun ensemble de sommets S est une couverture de sommets de G ssi les éléments correspondants forment un ensemble de frappe dans linstance densemble de frappe.
Commentaires
- Bienvenue dans ComputerScience @ SE. Utilisation intéressante du symbole spécial
∈– il est courant dutiliser MathJax, permettant, par exemple, un indice approprié: $ B_1, \ dots, B_m $. - et si la taille de Se est supérieure à 2? Cela fonctionnera-t-il?
Réponse
Le problème de jeu de frappe est équivalent au problème de couverture de jeu, qui est défini comme suit:
INPUT: une collection C de sous-ensembles dun ensemble fini S.
SOLUTION: Une couverture densemble pour S, cest-à-dire un sous-ensemble $ C « \ subseteq C $ tel que chaque élément de S appartient à au moins un membre de $ C « $.
Etant donné $ k $ existe-t-il un ensemble couvrant $ C » $ tel que $ \ vert C « \ vert \ leq k $?
Cela ressemble à un devoir, donc je vous laisse comprendre comment, étant donné une instance de Set Cover, vous pouvez le convertir en une instance équivalente de Hitting Set.
Sinon, si vous voulez suivre lastuce, vous montrez dabord que Hit Set in dans $ NP $, qui reçoit une solution, vous pouvez le vérifier en temps polynomial.
Ensuite, vous montrez que étant donné un graphique $ G = (V, E) $, trouver une couverture de vertex de taille $ k $ équivaut à trouver un ensemble de frappe de taille $ k $. Autrement dit, si $ | E | = m $, vous pouvez créer une instance densemble de frappe avec le même nombre densembles.