# Does every NP problem have a poly-sized ILP formulation?

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.

• You should point out an example or give a more complete quote ;) May 15 '12 at 19:57
• 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
• @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
• @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? May 16 '12 at 15:43
• 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. Jul 24 '12 at 9:05