1
$\begingroup$

Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$

$$ax+by=c.$$

Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ then this problem is in $NC$. How about the converse?

  1. If this problem is in $NC$, then is $2D$ shortest vector in $NC$?

  2. If this problem is in $NC$, then is $GCD$ in $NC$?

Note $1$ implies $2$.

$\endgroup$

0

You must log in to answer this question.