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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.