How Do You Prove A Problem Is NPC
|
AllPages RecentChanges Links to this page Edit this page Search Entry portal |
|
|
|
How Do You Prove A Problem Is NPC |
|
||||
If we want to show that a specific problem, A, is NP-Complete (NPC) then we need to show that whenever we have a problem B that's in NP, problem A is at least as hard.
In other words, we need to show that we can transform B, our randomly chosen problem from P, into A. That means that every instance of B can be converted into an instance of A, and a solution to that instance can then be converted back into a solution to the original instance.
In the following discussion I'll work with specific examples to help make the concepts clear. In particular, I'll use Graph Three-Colouring as the problem I claim to be NPC, and use integer factorisation as a specific example of a problem from NP.