sci.op-research

Gordon Sande wrote:
> 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.
>
>
>

As far as I know (and I'm no expert -- this stuff makes my eyes water),
NP-hardness is a property of the problem rather than the formulation. I
completely agree that (a) just because someone has an IP formulation for
a problem, that does not make it NP-anything and (b) one should eye
claims of NP-whatever carefully. As far as making such claims to hype
the problem, though, I think there are two other factors to consider.

First, for reasons I don't entirely understand, some people feel
_obligated_ to note that their problems are NP-this or NP-that, perhaps
fearing the wrath of a reviewer. If I'm trying to publish a new
algorithm for a problem, I usually (not always) ignore the NP stuff and
just point out that my algorithm is (allegedly) faster than what's out
there, and that the time difference is nontrivial on practical
instances. I don't care if the solution time is asymptotically
polynomial, since as far as I know nobody solves asymptotically infinite
instances anyway. :-) Either "real-life" sized problems take a while,
or they don't, and in the latter case there's no need for a new algorithm.

Second, I think a lot of people out there understand NP-ness even less
than I do, and as I said this stuff makes my head spin. So the notion
that any IP problem must be NP-something, the related confusion between
formulation and problem, and the resulting occasional "promotion" of a
class P problem to class NP may be covered by a quote I've seen ascribed
to Napoleon Bonaparte: "Never ascribe to malice, that which can be
explained by incompetence."

Personally, I only believe assertions of NP-whatever if either the
author can cite a (credible) reference particular to that problem class,
or can demonstrate a polynomial-time conversion to a known NP-something
problem. [Disclaimer: I've done the former myself.]

One last comment: I frequently see assertions of NP-ness intended as a
justification for why a heuristic is suitable (i.e., why optimality need
not be required). Too often the assertion of NP-ness, while quite
possibly correct, is not accompanied by any evidence that actual
"real-life" problems take an unacceptably long time to solve to
optimality. NP-hardness and NP-completeness say that solution times
will grow faster than any polynomial bound (unless it turns out that P =
NP). They don't say that a specific problem instance is going to take
forever to solve.

/Paul