How Do You Prove A Problem Is NPC

Links to this page
Edit this page
Entry portal
Advice For New Users

Prev: What is NP-Complete

Proving a problem is NP-Complete

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.

Next: Graph Three-Coloring is NPC
Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout