Edit made on December 11, 2016 by ColinWright at 11:37:22
Deleted text in red /
Inserted text in green
MM
WM
HEADERS_END
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