No common terms between polynomials: an efficient check?
Here is an approach that might occasionally be a bit better in practice, but is still exponential-time in the worst case, so it is not a satisfying answer to your question.  Suppose we want to determine whether the polynomials $f(x,y,\dots),g(x,y,\dots)$ have a common term.  First write

$$\begin{align*}
f(x,y,\dots) &amp;= f_0(y,\dots) + x f_1(y,\dots)\\
g(x,y,\dots) &amp;= g_0(y,\dots) + x g_1(y,\dots).
\end{align*}$$

Then recursively check whether $f_0,g_0$ have a common term; and check whether $f_1,g_1$ have a common term.

To express $f$ in that format, note that

$$f_0(y,\dots) = f(0,y,\dots)$$

so it suffices to plug in $x=0$ into the expression for $f$ to get an expression for $f_0$.  Try to simplify that expression as much as possible using standard rules for simplifying polynomials.  Then, you can write

$$f_1(y,\dots) = (f(x,y,\dots) - f_0(y,\dots))/x.$$

Simplify that expression as much as possible.

If no simplification is done, the running time is exponential in $n$, the number of variables.  We obtain a recurrence of the form $T(n) = 2 T(n-1) + O(1)$, so the worst-case running time is exponential.  The room for hope is that if simplification is done at each stage, it's possible that for some inputs this might be faster than that.  In general it will still be exponential-time in the worst case, though, so I don't know whether this will actually be any better in practice.