Algorithm to check two binary expression trees for equivalence

Question

Is there any known algorithm to check for equivalence of two binary expression trees over a field $\mathbb{F}$?

For example for the expression $a+b = b+a$ it should return true (since $\mathbb{F}$ is commutative) and $a^b = b^a$ should return false as well as for $a^2 = a$.

I can think of a naive implementation which is basically brute-force creating all equivalent binary expression trees for LHS and for RHS and check for a non empty intersection.

Is there a real-world-efficient algorithm to do this? I mean it isn't a must to be polynomial time but will work fast for common or relatively small problems (trees with at most ~100 nodes).

Wikipedia doesn't give any reference to the problem of comparing two for equivalence over some algebraic structure.

Answer 1

The answer depends heavily on what operations you allow to appear in the trees.

If the tree uses only addition, subtraction, and multiplication, this is an instance of the polynomial identity testing problem, which can be solved in polynomial time by a randomized algorithm. Basically, you pick random values for $a,b$ and check whether both trees return the same value; and repeat a few hundred times. See https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma and Is there an efficient algorithm for expression equivalence?.

Division can also be handled by expressing the tree as a rational polynomial (ratio of two polynomials), then again using polynomial identity testing.

If you can have addition, subtraction, multiplication, division, and exponentiation, then I don't know whether there are efficient algorithms. I think that problem, or some variant of it, is addressed here: Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials.

---

(Possibly loosely related: Decidability of Equality of Radical Expressions)

Let me also highlight that expressions like $a^b$ "smell fishy" and don't typecheck when $a,b \in \mathbb{F}$ are elements of a finite field. For instance, if $\mathbb{F}=GF(p)$, then exponentiation $a^b$ is well-defined if $a$ is taken modulo $p$ and $b$ is taken modulo $p-1$ (not modulo $p$). In particular, $(a+p)^b=a^b$ modulo $p$, but $a^{b+p} \ne a^b$ modulo $p$. So, to make an expression like $a^b$ make sense, $a^b$ has to be interpreted as $a^{f(b)}$ where $f$ maps from elements of $GF(p)$ to numbers $\{0,1,\dots,p-2\}$. There is a natural way to do that, e.g., $f(0)=0$, $f(1)=1$, ..., $f(p-2)=p-2$, $f(p-1)=0$. But then when you do that, exponentiation doesn't have the properties you might expect. In particular, $a^{b+c}$ is no longer equal to $a^b \times a^c$. For instance, if $b=1$ and $c=p-1$, then $a^{b+c}=a^{p-1+1}=a^0=1$, but $a^b = a^1 = a$ and $a^c = a^{p-1} = 1$, so $a^{b+c}=1$ but $a^b \times a^c = a$. So I would be pretty suspicious of any expression that contains exponentiation where the expression in the exponent is an element of $\mathbb{F}$.