This question must be well known but I cannot find it in the literature. 


Question: What is the computational complexity of the word problem in a subring of the ring of polynomials in $n\ge 1$ variables ring over rationals? Is it in $P$?


Thus we fix $m$ polynomials $f\_1,...,f\_m$ from $\mathbb{Q}[x\_1,...,x\_n]$ Then for every polynomial $g(y\_1,...,y\_m)$ over $\mathbb{Q}$, we need to check if the polynomial $g(f\_1,...,f\_m)$ is 0. The size of the input is the amount of space needed to write down $g$.


 **Update**  I was thinking about the following algorithm: we need to check that $g(f\_1,...,f\_m)=0$. First plug in $x\_i=0$ and check that the result is 0. It is easy. Then take the derivative $\partial g(f\_1,...,f\_m)/\partial x\_i$ and plug in 0's there, etc. The number of possible derivatives is polynomial in the size of $g$, and the length of the computation seems to be polynomial in the size of $g$ also. We need to pre-compute enough products of values of $f\_i$ and their derivatives at 0. Does this algorithm ran in polynomial time? Is it well-known, and if so what is a reference?



The word problem in the ring of polynomials
I'm going to summarize what is said in the comments and my own remarks about the update, to make a complete answer:


The algorithm suggested in the update is basically checking lower-order coefficients of the composition. Certainly if the exponents are in binary, then the algorithm doesn't work: It takes exponential time to distinguish $x^n$ from $0$. Even if the exponents are in unary, it takes exponential time to distinguish $x\_1x\_2\ldots x\_n$ from $0$.


The [paper of Ibarra and Moran](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.5387&rep=rep1&type=pdf) places a more general problem, the word problem in the sense of circuits or straight-line programs, in co-RP.


A straight-line program is a sequence of formulas arranged like a tax form. It's a sequence of intermediate variables defined by formulas. It's equivalent to an arithmetic circuit. It's an interesting definition for groups as well as for polynomial arithmetic. It is more general than the stated question because it's easy to decompose a polynomial with listed terms into a circuit --- the only hard part is exponents in binary and you can do that by squaring up --- and composition of polynomials can be implemented in a straight-line program by the definition of a straight-line program.


The complexity class BPP means yes-no questions answered in polynomial time by a randomized algorithm which gives a probably-correct answer, with probability $p > c > 1/2$. The complexity class RP is the same thing, except that if the program answer yes, it is certainly correct; if it answers no, it is only probably correct. The probability of correctness can be amplified to very close to 1. It is a well-known conjecture that BPP = P, and obviously BPP contains RP and RP contains P. The basis of the conjecture is that good pseudo-random number generators seem to exist. However, there are strong theoretical reasons that even RP = P is a very hard conjecture.


Ibarra and Moran give a polynomial-time algorithm in RP to show that an arithmetic circuit over $\mathbb{Q}$ (say) is non-zero. (So there is an algorithm in co-RP that the circuit *is* zero -- this is just switching "yes" and "no".) The algorithm consists of plugging in large values at random. It is a bit easier to see what they do over $\mathbb{Z}$, and not really different because you can reduce $\mathbb{Q}$ to $\mathbb{Z}$ by decomposing fractions into numerators and denominators. They make an exponentially large box in $\mathbb{Z}^n$, and they show that if the circuit is non-zero, then it is usually non-zero in the box, using simple (but skillful) counting estimates for zero values.


[Kabanetz and Impagliazzo](http://dx.doi.org/10.1007/s00037-004-0182-6) show that some of the same strong theoretical difficulties that obstruct the conjecture that BPP = P or RP = P, also make it hard to test circuit equality in P. So you should recognize Ibarra-Moran as efficient in practice because it is in co-RP, believe that Ibarra-Moran can be converted to P using pseudo-random numbers, and be satisfied that no one can provably find any algorithm for the problem in P.


