Papadimitriou in https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf shows ILP is fixed parameter tractable in number of constraints and Lenstra in https://people.csail.mit.edu/rrw/presentations/Lenstra81.pdf shows ILP is fixed parameter tractable in number of variables. It is shown in https://dl.acm.org/doi/10.5555/284943.284957 that two variable integer programming is equivalent to GCD but the program has an objective function.

What about the case of deciding

$$\exists x\in\mathbb Z^d$$ $$Ax\leq b$$

when number of variables and number of constraints are both fixed?

Is this in $NC$?

  • $\begingroup$ If both variables and constraints are fixed then the only complexity is in the bits of $A,b$. Just making sure that this is the problem you wish to understand. $\endgroup$ Oct 2 at 19:54
  • $\begingroup$ @ChandraChekuri The bit length of the entries of A and b could be large and not fixed. So complexity is in number of bits to encode $A$ and $b$. $\endgroup$
    – Turbo
    Oct 3 at 2:15
  • $\begingroup$ This is probably a stretch, but Levin mentions some old results about how factoring can be done in polynomial time in a model that allows constant-time arithmetic on arbitrarily large integers (I think). E.g. using repeated squaring to get exponentially large integers. Maybe similar ideas could be used to show that your problem is likely to be hard. $\endgroup$
    – Neal Young
    Oct 14 at 0:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy