<p>Papadimitriou in <a href="https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf" rel="nofollow noreferrer">https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf</a> shows ILP is fixed parameter tractable in number of constraints and Lenstra in <a href="https://people.csail.mit.edu/rrw/presentations/Lenstra81.pdf" rel="nofollow noreferrer">https://people.csail.mit.edu/rrw/presentations/Lenstra81.pdf</a> shows ILP is fixed parameter tractable in number of variables. It is shown in <a href="https://dl.acm.org/doi/10.5555/284943.284957" rel="nofollow noreferrer">https://dl.acm.org/doi/10.5555/284943.284957</a> that two variable integer programming is equivalent to GCD but the program has an objective function.</p>
<p>What about the case of deciding</p>
<p><span class="math-container">$$\exists x\in\mathbb Z^d$$</span>
<span class="math-container">$$Ax\leq b$$</span></p>
<p>when number of variables and number of constraints are both fixed?</p>
<p>Is this in <span class="math-container">$NC$</span>?</p>

CC BY-SA 4.0
2022-10-02T19:54:50.157Z
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.
Chandra Chekuri
CC BY-SA 4.0
2022-10-03T02:15:51.863Z
@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$.
Turbo
CC BY-SA 4.0
2022-10-14T00:49:20.763Z
This is probably a stretch, but Levin [mentions](https://www.cs.bu.edu/fac/lnd/expo/qc.htm) 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.
Neal Young
<cc.complexity-theory><complexity-classes><linear-programming><dc.parallel-comp><integer-programming>
Parallel complexity of fixed dimension fixed constraints integer programming
Turbo
# Parallel complexity of fixed dimension fixed constraints integer programming

(Asked by: username_0 on 2022-10-02)

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

**Tags:** cc.complexity-theory, complexity-classes, linear-programming, dc.parallel-comp, integer-programming
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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$.  
> **username_2**: This is probably a stretch, but Levin [mentions](https://www.cs.bu.edu/fac/lnd/expo/qc.htm) 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.  

---

## 0 answers

