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