Is there an efficient algorithm for expression equivalence?

Question

e.g. $xy+x+y=x+y(x+1)$ ?

The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or division. Letters are variables.

If it helps, we can forbid any expression representable with numeric values other than $1$; i.e. not $x^2$ nor $3x$ nor $4$:

• multilinear, no powers other than $1$: $x+xy \equiv x^1+x^1y^1$ is OK, but not $x^2+x^3y^4$, and not anything that could be represented as that, as in a full expansion to sum-of-products e.g. not $x(x+y) \equiv x^2+y$;
• all one, no coefficients other than $1$: $x+xy \equiv 1.x+1.xy$ is OK, but not $2x+3xy$, and not anything that could be represented as that, as in a full expansion to sum-of-products e.g. not $a(x+y)+x(a+b) \equiv 2ax+ay+bx$ ; and
• no constants other than $1$: again, in the fully expanded sum-of-products e.g. not $(a+1)+(b+1) \equiv a+b+2$

$Q.$ Is there an efficient algorithm to determine if two expressions are equivalent?

---

To illustrate, here's an inefficient brute-force algorithm with exponential time:

expand both expressions fully to sum-of-products, which can easily be checked for equivalence (just ignore order, since commute/associate can reorder).

e.g.
$(a+b)(x+y) \rightarrow ax+ay+bx+by$
$a(x+y)+b(x+y) \rightarrow ax+ay+bx+by$

---

This seems a well-known problem - even high school students are taught manual ways to solve it. It's also solved by automated theorem provers/checkers, but they concentrate on more sophisticated aspects.

Here's a working online automated theorem prover: http://tryacl2.org/, which shows equivalence by finding a sequence of commute/associate/distribute etc:

$xy+x+y=x+y(x+1)$ ?
(thm (= (+ (* x y) x y) (+ x (* y (+ x 1))) )) --- 188 steps

$y+x(y+1)=x+y(x+1)$ ?
(thm (= (+ y (* x (+ y 1))) (+ x (* y (+ x 1))) )) --- 325 steps

This is my first question here, so please let me know if I've chosen the wrong place, wrong tags, wrong way of describing/asking etc. Thanks!
NB: this question has been rewritten in response to comments
Thanks to all responders! I've learned a lot.

Answer 1

Your problem reduces to zero testing of multivariate polynomials, for which there are efficient randomized algorithms.

Your expressions are all multivariate polynomials. Apparently, your expressions are built up by the following rules: (a) if $x$ is a variable, then $x$ is an expression; (b) if $c$ is a constant, then $c$ is an expression; (c) if $e_1,e_2$ are expressions, then $e_1+e_2$ and $e_1e_2$ are expressions. If that's indeed what you intended, every expression is a multivariate polynomial over the variables.

Now, you want to know if two expressions are equivalent. This amounts to testing whether two multivariate polynomials are equivalent: given $p_1(x_1,\dots,x_n)$ and $p_2(x_1,\dots,x_n)$, you want to know if these two polynomials are equivalent. You can test this by subtracting them and checking whether the result is identically zero: define

$$q(x_1,\dots,x_n) = p_1(x_1,\dots,x_n) - p_2(x_1,\dots,x_n).$$

Now $p_1,p_2$ are equivalent if and only if $q$ is the zero polynomial.

Testing whether $q$ is identically zero is the zero testing problem for multivariate polynomials. There are efficient algorithms for that. For instance, one example algorithm is to evaluate $q(x_1,\dots,x_n)$ at many random values of $x_1,\dots,x_n$. If you find a value of $x_1,\dots,x_n$ such that $q(x_1,\dots,x_n)$, then you know that $q$ is not identically zero, i.e., $p_1,p_2$ are not equivalent. If after many trials they are all zero, then you can conclude that $q$ is identically zero (if $q$ is not identically zero, the probability that all of those trials yield zero can be made exponentially low). The number of iterations you need to do is related to the degree of $q$; see the literature on polynomial identity testing for details.

For instance, see https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma and http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/

These algorithms apply if you are working over a finite field. You didn't state what field/ring you are working in, and whether you are are treating these expressions as formal expressions (e.g., polynomials as abstract objects) or as functions from $\mathbb{F}^n \to \mathbb{F}$. If you are working over a finite field, the methods above apply immediately.

If you're treating the expressions as formal objects, then your expressions are equivalent to multivariate polynomials with integer coefficients. You can test equivalence of these by choosing a large random prime $r$ and testing equivalence modulo $r$, i.e., in the field $\mathbb{Z}/r\mathbb{Z}$. Repeat this polynomially many times, with different random values of $r$, and you should get an efficient randomized algorithm for testing equivalence of these formal expressions.

Answer 2

To follow up on the one-power, one-coefficent and one-constants constraints in the question:

These define a subset the problem of polynomial identity testing. Clearly, they can be solved with a technique that solves the general problem. The question is whether they form a subset that is more easily solved.

one-coefficient: in problems without this, terms might be combined, making the problem easier. Consider the Binomial Theorem/Pascal's triangle for $(a+b)^n$. This can be expanded one factor at a time, producing terms with overlapping orders e.g. $(a+b)(a+b) = aa+ab+ab+bb = aa+2ab+bb$ The fewer terms make it easier to expand with the next factor: $(aa+2ab+bb)(a+b) = aaa+2aab+abb + aab+2abb+bbb = aaa+3aab+3abb+bbb$ and again terms are combined, making a smaller simpler problem. This combining of terms is a form of dynamic programming.

That is, the possibility of combining terms, creating a non-one coefficient, makes the problem easier not harder.

(Although there is more work in calculation in multiplying non-one coefficients)

non-one constants are included in the above argument by considering constants as variables with zero exponent.

one-power I don't think this makes any difference. Although non-one exponents can be created in more than one way (e.g. $a^4=a^2a^2=a^1a^3$), and this can lead to overlap and combination (as in the Binomial Theorm/Pascal's triangle above), actual combination is only possible if non-one coefficients are allowed.

The above is not a formal or rigorous argument. It rests on an assumption about what makes the problem difficult. But it does seem to me that combining terms only makes for an easier problem - so preventing this by the one coefficient constraint is not going to make the subset easier.