# Algorithm to check two binary expression trees for equivalence

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.

• Is $\mathbb F$ some arbitrary fixed finite field? 1) $a^2 = a$ in $\mathbb F_2$. 2) You can express boolean formulas as polynomials, so your problem is at least NP-hard, by reduction from SAT.
– user114966
May 6 '21 at 19:40

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?.
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}$$.