Return to Question

1. Given $a,b\in\mathbb N$ find $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.

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.

Problem $1$: Given $U,V,N$ deciding if there is a solution to $XY=N$ with $X\in[U,V]\cap\mathbb Z$ is $NP$-hard.

Problem $2$: Given $N$ finding an $X,Y\in\mathbb Z_{>1}$ such that $XY=N$ without other restrictions to $X,Y$ is a candidate functional $NP$- intermediate problem.

Problem $3$: Given a bivariate quadratic equation over $aX^2+bY=c\in\mathbb Z[X,Y]$ deciding if there is a $X,Y\in\mathbb N$ satisfying the equation is $NP$-complete.

All the problems above $P$ and below $NP$ described before where from bivariate quadratics.

Problem $4$: Given integers $a,b\in\mathbb N$ the problem of finding $GCD(a,b)$ is a candidate functional $P$-intermediate problem. It can be given as finding $X,Y,Z\in\mathbb Z$ such that $GCD(X,Y)=1$ and $Z|a$ and $Z|b$ and $Xa+Yb=Z>0$ holds and for all $Z'>Z$, $Z'^2\nmid ab$.

Problem $5$: Given integers $a,b,c\in\mathbb N$ the problem of $X,Y\in\mathbb Z$ such that $aX+bY=c$ is a candidate functional $P$-intermediate problem.

Problem $5$ is a bivariate linear Diophantine problem.

There is an $FP$-reduction from problem $5$ to problem $4$ given by the Euclidean algorithm. That is Euclidean algorithm for $GCD(a,b)$ solves problem $5$.

1. If Problem $4$ were to be in functional $NC$ would it provide a functional $NC$ solution to problem $5$? Problem $5$ seems a little bit hard for functional $NC$ compared to problem $4$.

But is it so?

2. Will problem $5$ in functional $NC$ provide functional $NC$ solution to problem $4$? Definitely it provides $NC$ solution for testing $GCD$ is $1$ (coprimality). But for general $GCD$ problem it is not clear.

3. Is there a variant of problem $4$ or problem $5$ which signifies $P$-completeness? I would like to keep the number of integer variables to be constant and degree of the equations involved to be $\leq2$.

1. Given $a,b\in\mathbb N$ find $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.

Problem $1$: Given $U,V,N$ deciding if there is a solution to $XY=N$ with $X\in[U,V]\cap\mathbb Z$ is $NP$-hard.

Problem $2$: Given $N$ finding an $X,Y\in\mathbb Z_{>1}$ such that $XY=N$ without other restrictions to $X,Y$ is a candidate functional $NP$- intermediate problem.

Problem $3$: Given a bivariate quadratic equation over $aX^2+bY=c\in\mathbb Z[X,Y]$ deciding if there is a $X,Y\in\mathbb N$ satisfying the equation is $NP$-complete.

All the problems above $P$ and below $NP$ described before where from bivariate quadratics.

Problem $4$: Given integers $a,b\in\mathbb N$ the problem of finding $GCD(a,b)$ is a candidate functional $P$-intermediate problem. It can be given as finding $X,Y,Z\in\mathbb Z$ such that $GCD(X,Y)=1$ and $Z|a$ and $Z|b$ and $Xa+Yb=Z>0$ holds and for all $Z'>Z$, $Z'^2\nmid ab$.

Problem $5$: Given integers $a,b,c\in\mathbb N$ the problem of $X,Y\in\mathbb Z$ such that $aX+bY=c$ is a candidate functional $P$-intermediate problem.

Problem $5$ is a bivariate linear Diophantine problem.

There is an $FP$-reduction from problem $5$ to problem $4$ given by the Euclidean algorithm. That is Euclidean algorithm for $GCD(a,b)$ solves problem $5$.

1. If Problem $4$ where to be in functional $NC$ would it provide a functional $NC$ solution to problem $5$? Problem $5$ seems a little bit hard for functional $NC$ compared to problem $4$.

But is it so?

2. Will problem $5$ in functional $NC$ provide functional $NC$ solution to problem $4$? Definitely it provides $NC$ solution for testing $GCD$ is $1$ (coprimality). But for general $GCD$ problem it is not clear.

3. Is there a variant of problem $4$ or problem $5$ which signifies $P$-completeness? I would like to keep the number of integer variables to be constant and degree of the equations involved to be $\leq2$.

Problem 6: Given $U,V,a,b\in\mathbb N$, is there a common divisor of $a,b$ in $[U,V]$?

4. What is the complexity of problem $6$? Is it even in $P$?

Problem $1$: Given $U,V,N$ deciding if there is a solution to $XY=N$ with $X\in[U,V]\cap\mathbb Z$ is $NP$-hard.

Problem $2$: Given $N$ finding an $X,Y\in\mathbb Z_{>1}$ such that $XY=N$ without other restrictions to $X,Y$ is a candidate functional $NP$- intermediate problem.

Problem $3$: Given a bivariate quadratic equation over $aX^2+bY=c\in\mathbb Z[X,Y]$ deciding if there is a $X,Y\in\mathbb N$ satisfying the equation is $NP$-complete.

All the problems above $P$ and below $NP$ described before where from bivariate quadratics.

Problem $4$: Given integers $a,b\in\mathbb N$ the problem of finding $GCD(a,b)$ is a candidate functional $P$-intermediate problem. It can be given as finding $X,Y,Z\in\mathbb Z$ such that $GCD(X,Y)=1$ and $Z|a$ and $Z|b$ and $Xa+Yb=Z>0$ holds and for all $Z'>Z$, $Z'^2\nmid ab$.

Problem $5$: Given integers $a,b,c\in\mathbb N$ the problem of $X,Y\in\mathbb Z$ such that $aX+bY=c$ is a candidate functional $P$-intermediate problem.

Problem $5$ is a bivariate linear Diophantine problem.

There is an $FP$-reduction from problem $5$ to problem $4$ given by the Euclidean algorithm. That is Euclidean algorithm for $GCD(a,b)$ solves problem $5$.

1. If Problem $4$ were to be in functional $NC$ would it provide a functional $NC$ solution to problem $5$? Problem $5$ seems a little bit hard for functional $NC$ compared to problem $4$.

But is it so?

2. Will problem $5$ in functional $NC$ provide functional $NC$ solution to problem $4$? Definitely it provides $NC$ solution for testing $GCD$ is $1$ (coprimality). But for general $GCD$ problem it is not clear.

3. Is there a variant of problem $4$ or problem $5$ which signifies $P$-completeness? I would like to keep the number of integer variables to be constant and degree of the equations involved to be $\leq2$.