Domanda su NP-Completezza del Set problema Independent

Question

Ho pensato che, quando dimostrando che un problema P è NP-completo, avremmo dovuto ridurre un problema noto NPC per P. Ma, guardando la soluzione al problema Independent Set, sembra di non andare in questo modo.

Per dimostrare che Independent Set è NP-completo, si prende un grafo G, trovare il suo inverso G 'e quindi calcolare Clique (G'). Ma, questo sta facendo il contrario:. Sta prendendo un problema P non so se si tratta di NPC e poi lo riduce ad un sapere problema NPC

Ecco s 'un esempio della soluzione.

Che cosa mi manca qui? Non è questo torto, dal momento che sta facendo il contrario?

Answer 1

Per dimostrare che P è NP-completo, abbiamo bisogno di mostrare due cose:

1. che P esiste in NP.
2. Che non c'è un algoritmo di riduzione polytime a ridurre alcuni problemi NP-completo Q a P.

Se sappiamo che CLIQUE è in NPC, allora si può facilmente dimostrare che IS è in NPC.

1. Possiamo verificare è banalmente in polytime. vertici iterazione, affinché ciascuno ha un bordo non nella soluzione candidato.
2. Abbiamo ora bisogno di ridurre il CLIQUE a IS. Dato un G grafico e un n intero, per CLIQUE vogliamo verificare se c'è una cricca di dimensioni n. Lasciate H sia l'inverso di G. Se si trova un IS in H di dimensioni n, si dispone di una cricca di dimensioni n in G con gli stessi vertici. Abbiamo ridotto CLIQUE a IS.

Se si dovesse ridurre IS per CLIQUE, si sarebbe non dimostra che uno dei due è in NPC a meno che non si potrebbe ridurre qualche altro problema in NPC per IS.

Answer 2

Credo che questa pagina può aiutare a http://mlnotes.com/2013/04 /29/npc.html