4
$\begingroup$

  1. Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$.

  2. Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$.

Euclidean algorithm solves both.

My question is if either 1 or 2 is in functional $NC$ does it follow the other is in functional $NC$?

Is there a variant of $1$ or $2$ which is $P$-complete? Ideally I would like the involved Diophantine equations to be of constant number of variables and constant degree.

Improve this question
$\endgroup$

0

Reset to default

You must log in to answer this question.