Most recent change of HowDoYouProveAProblemIsNPC

Edit made on December 11, 2016 by ColinWright at 11:37:22

Deleted text in red / Inserted text in green

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