2
$\begingroup$

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$?

Improve this question
$\endgroup$
3
  • $\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$
    – Chandra Chekuri
    Commented Oct 2, 2022 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
    Commented Oct 3, 2022 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
    Commented Oct 14, 2022 at 0:49

0

Reset to default

Your Answer

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