sci.op-research

On 2008-04-13 09:32:04 -0300, saneman said:

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

The general rule goes something like "if it looks like an IP but because of
its special structure it turns out to not be NP then it will be given a
different name". There are many instances of claims that because the first
attempt at stating a problem was as an IP then the problem must be NP. All
too often later attempts at the same problem show this to have been a wild
and totally unjustified leap of logic. Claiming something is NP is too
often hype intended to make the problem look more difficult, important,
worthy of tenure, suitable for being a thesis topic or whatever.

In one case I read a technical report on some problem that was formulated as
an IP and thus claimed to be NP. The followup technical report gave a linear
algorithm for the problem based on a more detailed analysis of the problem.
So my cynicism has some basis in observed behavior. I tend to view most claims
of a new problem being NP as a description of the formulation rather than as
an actual property of the problem. It is too bad that it has come to such a
state.

Your observation is correct so keep reading the fine print.