Given two multivariate polynomials over a unique factorization domain R of at most n terms, is it possible to find the greatest common divisor in polynomial time with respect to n?
I have skimmed a few papers related to the polynomial greatest common divisor but failed to find any argument about the time complexity of the algorithm.
If it is not NP-hard. I'm also interested in the problem of finding GCD between two algebraic expressions that consist of only standard additions, multiplications, exponentiations, paratheses, real numbers, and variables. For example:
$$x^2(x+2y)^2+y^2(y+2x)^2-2x^2y^2,$$ $$(x^2-1)^2-(y^2-1)^2+2(xy+1)(x+y)(x-y)$$
The greatest common divisor of the above two formulae is $(x+y)^3$.
Is this problem NP-hard with respect to the number of variables and operators used to describe the expression? I guess it is because computing the expansion itself could be NP-hard as the number of terms in the expansion can grow exponentially as the length of expressions grows. But I have no argument about why computing GCD has to be performed on the expansion.
What I need eventually is to prove a problem that is harder than the above two is NP-hard. Any argument about the hardness of the above problems or similar problems (with looser constraints) could help.