Pergunta sobre o NP-completude do problema do conjunto independente

Question

Eu pensei que, ao provar que um problema P é prematuro de NP, deveríamos reduzir um problema conhecido do NPC para P. Mas, olhando para a solução para o problema do conjunto independente, parece não seguir esse caminho.

Para provar que o conjunto independente é NP-Coplete, você pega um gráfico G, encontra seu G 'inverso e, em seguida, calcule a clique (G'). Mas isso está fazendo o contrário: está levando um problema, o Pi não sabe se é o NPC e depois o reduz a um problema de conhecimento do NPC.

Aquié um exemplo da solução.

O que estou perdendo aqui? Isso não está errado, já que está fazendo o contrário?

Answer 1

Para provar que P é NP-Coplete, precisamos mostrar duas coisas:

1. Esse P existe no NP.
2. Que existe um algoritmo de redução de poli-tempo para reduzir algum problema de preenchimento de NP q a P.

Se soubermos que o CLIC está no NPC, podemos provar facilmente que está no NPC.

1. Podemos verificar é trivialmente no poliTime. Os vértices itera, verifique se cada um tem uma borda não na solução candidata.
2. Agora precisamos reduzir a camarilha para IS. Dado um gráfico G e um número inteiro n, para clique, queremos verificar se há uma camarilha de tamanho n. Deixar H ser o inverso de G. Se você encontrar um está em H de tamanho n, você tem uma camareira de tamanho n dentro G com os mesmos vértices. Nós reduzimos a camarilha para IS.

Se você reduzia é para clique, você não provaria que qualquer um deles está no NPC, a menos que possa reduzir algum outro problema no NPC.

Answer 2

Eu acho que esta página pode te ajudar http://mlnotes.com/2013/04/29/npc.html