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$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
