np-hard

1 definition found

np-hard - Free On-line Dictionary of Computing (26 May 2007) :

  NP-hard
  
     <complexity> A set or property of computational search problems
     .  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)