El problema del conjunto de golpes es NP completo

Prerrequisito: NP Completo

Problema : dado un conjunto base X de elementos y también una colección de agrupación C de subconjuntos disponibles en X y un número entero k , la tarea es encontrar el subconjunto más pequeño de X , tal que el subconjunto más pequeño, H ,coincida con todos los conjuntos comprendidos en C. Esto implica que la intersección de H y S es nula para todo conjunto S perteneciente a C , de tamaño ≤ k .

Prueba: una instancia del problema es una entrada especificada para el problema. Una instancia del Hitting Set es una colección C de subconjunto, S en X y k. Dado que un problema NP-completo, por definición, es un problema que es tanto NP como NP-Difícil , la prueba o afirmación de que un problema es NP-Completo consta de dos partes:

1. El problema en sí es NP-Complete.
2. Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso. (B es poli-tiempo reducible a C).

Si se cumple la única segunda condición, el problema se llama NP-Hard.
Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Es por eso que para mostrar que un problema es NP-completo, probar que el problema está en NP y cualquier problema NP-Completo es reducible a eso, entonces hemos terminado. Por lo tanto, se puede verificar que el problema del conjunto de golpes es NP-Completo usando las siguientes proposiciones:

1. Hitting Set está en NP: si cualquier problema está en NP, luego se le da un ‘certificado’, que es una solución al problema y una instancia del problema (un conjunto básico X, una colección, C de subconjuntos, S), nosotros podrá verificar (comprobar si la solución es correcta o no) el certificado en tiempo polinomial. Esto se puede hacer de la siguiente manera:
   Provisto un conjunto de aciertos, HS de tamaño k, verifique que cubra al menos un elemento en cada conjunto Si de X.
   Esto toma un tiempo polinomial, por lo tanto, en NP
2. Hitting Set es NP-Hard: Para demostrar que Hitting Set es NP-Hard, realizaremos una reducción a partir de la cual el problema de cobertura de vértices se puede reducir al problema de Hitting Set.

En el problema de cobertura de vértices , tenemos un gráfico G = (V, E)
Ahora, sea X, ese es el conjunto base = vértices de G. Eso es X = V(G) y la colección C del subconjunto Si en X es S _i = {u, v} es una arista en el gráfico G.

Ahora, se cumplen las siguientes propiedades:

• Si VC es la cubierta de vértice del grafo G de tamaño k , esto implica que para cada arista {u, v} u o v pertenece a VC. Por lo tanto, VC forma el Hitting Set porque todos los subconjuntos formarán una intersección con los vértices en VC.
• Si HS golpea un conjunto de X de tamaño k . Ahora, dado que HS intersecta cada subconjunto de X, al menos uno de los extremos de cada borde {u, v} debe pertenecer a la solución. Por lo tanto, abarca al menos un vértice para cada borde, por lo que forma VC.

Conclusión:

El problema del conjunto de golpes es NP y NP-Hard . Por lo tanto, el problema del conjunto de golpes es NP-Completo .