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:

- Calculate f(x)
- 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