sci.op-research
back to index
Group: sci.op-research
From: Mark Thornton
Date: Sunday, April 13, 2008 1:05 PM
Subject: Re: Are all IP problems NP-hard?
From: Mark Thornton
Date: Sunday, April 13, 2008 1:05 PM
Subject: Re: Are all IP problems NP-hard?
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.
Matching problems are an example of an IP which is polynomial.
Mark Thornton
