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.)