## 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

MM
WM
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