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$.
- 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?
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.
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]$?
- What is the complexity of problem $6$? Is it even in $P$?