The concept of NP-Hard is, as its name suggests, kind of hard to grasp. Here's the idea: some problems are reduceable to other problems. For instance, solving a linear equation like ax + b = 0 is reduceable to the problem of solving quadratic equations by stating the problem as 0x2 + ax + b = 0.

A given problem is NP-Hard if it takes at least as long as every other problem in the NP complexity class. That means that you can reduce any problem in NP (which stands for "nondeterministic polynomial time") to the original problem in polynomial time.

NP-Hard is not the same as NP-Complete. For a problem to be NP-Complete, it must be NP-Hard and be verifiable in polynomial time. That is, if you are given a possible answer, you can use an algorithm that takes O(nk) steps to determine if the answer is correct. The NP-Complete node has a little more thorough explanation if your mind's not blown already.

I agree with ApoxyButt that this can be hard to understand, but it might be a bit easier if you know what "hard" means in this case.

The most common reason for trying to find out if a problem (or set of problems) is NP-hard is in trying to determine if the problem is NP-complete. In set theory "complete", "hard" and "reducible" are ways of defining relations between different sets. One definition that applies to NP-hard problems is:

Definition 1:The set A is hard for a class of sets L iff every set in L is many-to-one reducible to A.

So, what does that mean? First we have to know what "Many-to-one reducible" means.

Definition 2: C is many-to-one reducible to D iff there is a function f(x) such that x is in C iff f(x) is in D

What definition 2 tells us is that if we know how to determine membership in D, and C is reductible to D, we know how to determine membership in B by using this algorithm:

  1. Calculate f(x)
  2. Determine if the result is in D

If the complexity of this function f(x) is less than that of checking for membership in D then we can say that D is no more complex than C.

If we apply this knowledge to definition 1 we are saying that if we know how to determine membership in set A we also know how to determine membership in any set in L using a set of fuctions that reduce the sets in L to A.

If we say that L is the class of problems called NP then by saying that A is hard for NP we mean that A is at least as complex as any other problem set in NP.

Note: As I mentioned above: just proving that a problem is NP-hard is not very useful and is normally only a step towards proving NP-completeness. The difficult part is finding the reducibility functions (f(x) above) that are no more complex than NP. See many-to-one polynomial-time reducible

Log in or register to write something here or to contact authors.