From: oliver@oak.math.ucla.edu (Mike Oliver)
Newsgroups: sci.math,sci.stat.math
Subject: Re: [Q]: what does the term "np hard" mean ?
Date: 19 Apr 1995 18:58:56 GMT

In article <3n2aa5$2hl@agate.berkeley.edu> schmid@rikers.CS.Berkeley.EDU (Scott Schmidler) writes:

>At the risk of offending the theoreticians, paraphrased it means that the
>problem is both non-polynomial in the size of the input, and not provably
>reducible to the class of NP-complete problems.  Ie it's at least as hard
>as NP-complete problems, but maybe harder.  The distinction being important
>because a polynomial solution to any NP-complete problem would yield a poly.
>solution to *all* NP-complete problems by reduction, but might still not
>help for NP-hard problems.  

Two minor criticisms.  The first is that you've assumed without mentioning
it that P != NP, but that's a *really* minor criticism since this assumption
must be a de facto axiom by now.  More seriously, you seem to be excluding
NP-complete problems from NP-hard and I don't think that's standard usage.

My understanding is that a problem is NP-hard if any NP problem can be
reduced to it in polynomial time.  A problem is NP-complete if it's
both NP-hard and NP.

(Side note:  some readers may have the impression that "NP" means 
"non-polynomial"; i.e. that it says a problem is hard.  That's not
correct; "NP" is short for "non-deterministic polynomial" and a problem
that's *not* NP is harder than one that is.  Roughly a problem is NP
if you can guess the answer and check your guess in polynomial time.)