Source : Free On-Line Dictionary of Computing

NP-hard
     
         A set or property of computational {search
        problem}s.  A problem is NP-hard if solving it in {polynomial
        time} would make it possible to solve all problems in class
        {NP} in polynomial time.
     
        Some NP-hard problems are also in {NP} (these are called
        "{NP-complete}"), some are not.  If you could reduce an {NP}
        problem to an NP-hard problem and then solve it in polynomial
        time, you could solve all NP problems.
     
        See also {computational complexity}.
     
        [Examples?]
     
        (1995-04-10)