sci.op-research

saneman wrote:
> I have read that all IP problems are NP-hard. But does it not depend on
> the instance?
>
> I assume that if they are all NP-hard they are not necessary NP-complete.

Gordon Sande is on target with his response. I just want to point out
that "instance" typically refers to an application of a particular
problem, not a problem class. In other words, an "instance" is a
problem class plus the data used to parameterize it.

I make that distinction because NP-whatever is defined in terms of the
problem class, not a particular problem instance. For example, the
knapsack problem is NP-hard. An instance of the knapsack problem with
three items have specified weights and values, and a specified capacity
for the knapsack, is not particularly difficult to solve, but that has
nothing to do with NP-hardness. One cannot say that this knapsack
problem is NP-hard while that knapsack problem is not.

NP-hard is in a sense worse than NP-complete. Basically, an NP-hard
problem is NP-complete if you can prove it's in the class NP, but in
general NP-hard problems are not required to be in NP.

/Paul