Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem in NP.

But I've seen papers on specific NP problems where people write things like "this is the first poly-sized formulation" or "there is no known poly-sized formulation". That's why I'm puzzled.

share|improve this question
8  
You should point out an example or give a more complete quote ;) –  hugomg May 15 '12 at 19:57
1  
There exists a polynomial reduction from every NP-complete problem to every other NP-complete problem. However, just because we know one exists doesn't mean we know how to construct it. –  Joe May 16 '12 at 5:05
3  
@Joe well, we know how to reduce any problem in NP to 3-sat, and also every practical NP-complete problem proof comes from a chain of reductions from 3-sat, so you can always compose reductions from any given NPC problem to any other. –  andy May 16 '12 at 5:53
10  
@andy didn't you just answer your question with that comment? You know every NP problem instance can be written as a polysized 3-SAT instance, and you know that a 3-SAT instance can be written as a polysized ILP instance, and polynomial applied to polynomial is another polynomial... what more do you expect from an answer? –  Artem Kaznatcheev May 16 '12 at 15:43
2  
When someone says that this is the first poly-size formulation, what they mean is that it is the first explicitly given such formulation. The reductions obtained through SAT (even if one takes care of all details) do not look nice and are hard to work with. We usually want formulations that are natural and easy to work with. –  Kaveh Jul 24 '12 at 9:05

2 Answers 2

This answer is mostly a recap of the comments on the question above.

If a problem is NP-complete, it can indeed be reduced to ILP, by using Karp's reductions (― Joe, andy). Claims of "polynomial sized formulations" from one problem to another, are likely meant as more direct formulations, as opposed to multiple reductions through SAT (― Kaveh).

share|improve this answer

Yes. Every NP problem has a polynomial-sized ILP formulation.

Here is why. Every NP problem has a polynomial-sized formulation as an instance of SAT. Moreover, all of the usual boolean operators -- logical OR, logical AND, logical NOT, etc. -- can be expressed in ILP, using a constant number of variables and inequalities per boolean operator. See Express boolean logic operations in zero-one integer linear programming (ILP) for details of how to do that. Thus, we get at most a constant-sized blow-up when going from SAT to ILP. This implies that there is a polynomial-sized formulation of every NP problem as an ILP problem.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.