Prev: Some Example NP Problems / Next: How do you prove a problem is NPC?
We start with NPHard
A problem H is "NPHard" if it's at least as hard
as every problem from NP. That means that if you
give me an instance, any instance, from a problem,
any problem, from NP, then I can convert it into
an instance of H such that a solution to that
instance can be converted back to a solution of the
original instance.
More specifically, consider Graph ThreeColouring (G3C),
and suppose I claim that G3C is NPHard. Now you come
along with a problem from NP. Perhaps you're interested
in integer factorisation. My claim that G3C is NPHard
means that whenever you have
a number n to factor, I can create a graph such that
threecolouring that graph lets me return to you a factor
of n.
Sounds unlikely? Perhaps, but it turns out to be true,
and is used as the example in the next section.
But to show that a problem is NPHard we must show that this
can be done for every NP problem. We must show that H
is at least as hard as every problem from NP. That's
rather a tall order, but we'll see how that works shortly.
But that's NPHard. What's NPComplete?
A problem is NPComplete if it is both itself in NP and
is also NPHard. In other words, it's (among) the hardest
of the problems in NPC.
Notice that this sortof assumes that there are
problems in NP that aren't in P. If not, the whole
thing collapses.
And that's the point of the "P vs NP" problem. 

So now we have an overview of this small part of the
complexity zoo.
 NPHard means at least as hard as everything in NP.
 There are problems in the intersection of NPHard and NP.
 These are called NPComplete.
 NP problems contain all P problems
In the next section we'll see how a problem can be proven to
be NPComplete.
Prev: Some Example NP Problems / Next: How do you prove a problem is NPC?
Links to this page /
Page history /
Last change to this page
Recent changes /
Edit this page (with sufficient authority)
All pages /
Search /
Change password /
Logout