<p>Fixed dimension linear integer programming being in NC would suggest that many other combinatorial optimization problems, where the problem's dimension is fixed, could also be in NC. It would imply that these problems could be solved more efficiently than currently possible using highly parallelizable algorithms.</p>

CC BY-SA 4.0
2023-06-24T20:37:48.957Z
2023-06-24T20:37:48.957Z
tomasantunes
<p>We know if fixed dimension linear integer programming is in <span class="math-container">$NC$</span> then integer <span class="math-container">$GCD$</span> is in <span class="math-container">$NC$</span>. Is this the only non-trivial implication of fixed dimension linear integer programming in <span class="math-container">$NC$</span>?</p>

<cc.complexity-theory><big-picture><big-list><dc.parallel-comp><integer-programming>
Problems which will be in $NC$ if fixed dimension Linear Integer Programming in $NC$
Turbo
# Problems which will be in $NC$ if fixed dimension Linear Integer Programming in $NC$

(Asked by: username_0 on 2018-12-16)

We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?

**Tags:** cc.complexity-theory, big-picture, big-list, dc.parallel-comp, integer-programming


---

## 1 answers

### Answer by username_1 on 2023-06-24. Score: -3

Fixed dimension linear integer programming being in NC would suggest that many other combinatorial optimization problems, where the problem's dimension is fixed, could also be in NC. It would imply that these problems could be solved more efficiently than currently possible using highly parallelizable algorithms.


---

