Pregunta sobre NP-completitud del conjunto de problemas Independiente

Question

pensé que, cuando se demuestra que un problema P es NP-completo, que se suponía que reducir un problema conocido de la APN a P. Pero, mirando a la solución al problema de ajuste independientes, parece no ir por este camino.

Para probar que conjunto independiente es NP-completo, se toma un grafo G, encontrar su inversa G 'y luego camarilla de cómputo (G'). Sin embargo, esto está haciendo al revés:. Que está teniendo un problema P No sé si se trata de la APN y luego lo reduce a un problema de la APN conocimientos

Aquí 's una ejemplo de la solución.

¿Qué me estoy perdiendo aquí? No es este mal, ya que lo hace al revés?

Answer 1

Para probar que P es NP-completo, tenemos que mostrar dos cosas:

1. que p existe en NP.
2. que hay un algoritmo de reducción polytime para reducir algunos problemas NP-completo Q a P.

Si sabemos que clique es en la APN, entonces podemos demostrar fácilmente que es, es en la APN.

1. Se puede verificar es trivialmente en polytime. vértices Iterar, asegúrese de que cada uno tiene un borde no en la solución candidato.
2. Ahora necesitan reducir CLIQUE a IS. Dado un grafo G y un n número entero, por CLIQUE queremos comprobar si hay una camarilla de tamaño n. Deje H sea la inversa de G. Si encuentra un SI en H de tamaño n, tiene una camarilla de tamaño n en G con los mismos vértices. Hemos reducido CLIQUE a IS.

Si se va a reducir la IS para pandilla, que no probaría que, o bien está en la APN a menos que usted podría reducir algún otro problema en la APN a IS.

Answer 2

creo que esta página puede ayudarle a http://mlnotes.com/2013/04 /29/npc.html