Editing HowDoYouProveAProblemIsNPC
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Tue Apr 23 21:39:58 2024.
Press
to finish editing.
Who can edit this page?
The World
Members
Council
Admin
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