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.

  • 8
    $\begingroup$ You should point out an example or give a more complete quote ;) $\endgroup$
    – hugomg
    May 15, 2012 at 19:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joe
    May 16, 2012 at 5:05
  • 3
    $\begingroup$ @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. $\endgroup$
    – andy
    May 16, 2012 at 5:53
  • 10
    $\begingroup$ @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? $\endgroup$ May 16, 2012 at 15:43
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jul 24, 2012 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).


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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