Since an easier class is included as a subset of a harder one, it is
helpful to have a notion of a language (i.e., problem) being among the
hardest possible within a class. Let X refer to either P, NP, PSPACE,
or EXPTIME. A language is called *X-hard* if every language
in class X is *polynomial-time reducible* to . In short,
this means that in polynomial time, any language in can be
translated into instances for language , and then the decisions for
can be correctly translated back in polynomial time to correctly
decide . Thus, if can be decided, then within a
polynomial-time factor, every language in X can be decided. The
hardness concept can even be applied to a language (problem) that does
not belong to the class. For example, we can declare that a language
is NP-hard even if
NP (it could be harder and lie in
EXPTIME, for example). If it is known that the language is both hard
for some class X and is also a member of X, then it is called *X-complete* (i.e., NP-complete, PSPACE-complete, etc.).^{6.8} Note that because of this uncertainty regarding P,
NP, and PSPACE, one cannot say that a problem is intractable if it is
NP-hard or PSPACE-hard, but one can, however, if the problem is
EXPTIME-hard. One additional remark: it is useful to remember that
PSPACE-hard implies NP-hard.

Steven M LaValle 2012-04-20