This in the definition of NPC. What you have to prove is that a language is in NPC.
This was proved for SAT first: http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
This was proved for SAT first: http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
No comments yet.