El problema del conjunto de golpes (HS) se define de la siguiente manera. Sea $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ colección del subconjunto de S ie $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Queremos saber si existe $ {S} «\ subconjunto S $ donde $ | {S} «| < k $ tal que $ S_i \ cap S «\ neq \ emptyset $, $ i = 1,2, …, m. $
Demuestre que HS es Np-Complete.
Pista : Cuando $ | S_i | = 2 $, HS se convierte en Vertex Cover, ya sé que es NP-complete.
Comentarios
- ¿Qué probaste? ¿Dónde lo hiciste? ' estamos felices de ayudarlo a comprender los conceptos, pero es poco probable que lo logre simplemente resolviendo los ejercicios. Puede encontrar esta página es útil para mejorar su pregunta.
Responder
3SAT se reduce a Hit Establezca un problema. Dado que 3SAT $ \ phi $ tiene $ m $ cláusulas y $ n $ variables, defina
$$ 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 {y} (y_1 \ lor y_2 \ lor y_3) \ text {es una cláusula.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {para todos variable} x. $$ $$ k = n $$
Suponga que $ \ phi $ es satisfactorio, entonces hay una asignación de valor verdadero para $ n $ variables. Entonces, agregue $ x $ a $ S «$ si $ x = true $, de lo contrario agregue $ \ overline {x} $ a $ S» $.
Ahora, suponga que el problema de HS tiene una solución $ S «$. Entonces, dado que para cada variable $ x $, $ S» \ cap S_x \ neq \ emptyset $, $ S «$ tiene al menos $ n $ literales de la forma $ x $ o $ \ overline {x} $ para cada variable $ x $. Además, ningún $ x $ y $ \ overline {x} $ pueden pertenecer a $ S «$ al mismo tiempo, ya que el tamaño de $ S» $ es como máximo $ n $. Además, para cada cláusula $ C_i $, $ S «\ cap S_i \ neq \ emptyset $ y entonces para cada cláusula seleccionamos $ y_i \ in S» \ cap S_i $, y establecemos $ x = verdadero $ si $ y_i = x $ y $ x = false $ if $ y_i = \ overline {x} $.
Comentarios
- ¿puedes mostrar una instancia positiva y una negativa?
Respuesta
Es fácil demostrar que Hitting Set está en NP. Una solución solo necesita exhibir el conjunto H – se puede verificar fácilmente en tiempo polinomial si H es de tamaño k y se cruza con cada uno de los conjuntos B1, …, Bm.
Reducimos desde la cobertura del vértice. Considere una instancia del vértice cubra el problema – grafica G = (V, E) y un entero positivo k. Lo asignamos a una instancia del problema del conjunto de golpes de la siguiente manera. El conjunto A es el conjunto de vértices V. Para cada arista e ∈ E, tenemos un conjunto Se que consta de los dos puntos finales de e. Es fácil ver que un conjunto de vértices S es una cubierta de vértice de G si los elementos correspondientes forman un conjunto de aciertos en la instancia del conjunto de aciertos.
Comentarios
- Bienvenido a ComputerScience @ SE. Interesante uso del símbolo especial
∈– es común usar MathJax, lo que permite, por ejemplo, un subíndice adecuado: $ B_1, \ dots, B_m $. - ¿Y si el tamaño de Se es mayor que 2? ¿Funcionará?
Respuesta
El problema del conjunto de golpes es equivalente al problema de la cobertura del conjunto, que está definido de la siguiente manera:
INPUT: una colección C de subconjuntos de un conjunto finito S.
SOLUCIÓN: Una cobertura de conjunto para S, es decir, un subconjunto $ C «\ subseteq C $ tal que cada elemento en S pertenece al menos a un miembro de $ C «$.
Dado $ k $, ¿existe una cubierta $ C» $ tal que $ \ vert C «\ vert \ leq k $?
Esto parece una tarea, así que te dejo averiguar cómo, dada una instancia de Set Cover, puedes convertirla en una instancia equivalente de Hitting Set.
De lo contrario, si Si desea seguir la pista, primero muestre que al presionar Establecer en $ NP $, que se le da una solución, puede verificarla en tiempo polinomial.
Luego, muestra que dado un gráfico $ G = (V, E) $, encontrar una cobertura de vértice de tamaño $ k $ es equivalente a encontrar un conjunto de impacto de tamaño $ k $. Es decir, si $ | E | = m $, puede construir una instancia de conjunto de impacto con la misma cantidad de conjuntos.