Nphard

1 definition found

From The Free On-line Dictionary of Computing (27 SEP 03) [foldoc]:

  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)