# Finding the distance between two polynomials (represented as trees)

A colleague who works on genetic programming asked me the following question. I first tried to solve it based on a greedy approach, but on a second thought, I found a counterexample to the greedy algorithm. So, I thought it's worth mentioning here.

Consider two polynomials which are represented by their expression trees. For instance, $$x^3-2x+1$$ and $$x^2 + 4$$ are illustrated below:

Rules:

1. Each node is either a variable name ($$x, y, z, \ldots$$), a number, or an operation (+,-,×).
2. The in-order traversal of the tree should result in a valid polynomial.
3. Operation nodes have in-degree 2. Other nodes have in-degree 0. All nodes have out-degree 1 (except root, whose out-degree is 0).

On a node N of the tree, define the basic operation as follows:

1. A basic operation can change the label of the node. For instance, $$x$$ can be changed to 3, or + can be changed to $$\times$$.
2. A basic operation can build an expression tree on top of N (see the example below).

The cost of the basic operation of type 1 is 1. The cost for type 2 is equal to the number of {+,-,×} operations in the newly built expression tree.

Example for type 2: The cost of the following basic operation is 2, since the expression tree built on top of node N uses two operations (- and ×).

Let T1 and T2 be two expression trees representing polynomials. Define the distance of T1 and T2 as follows: the minimum cost of basic operations for converting T1 to T2. Note that we don't require the converted tree to have the same structure as T2. We just want it to compute the same polynomial as T2. (See the comments for an example.)

The problem: Given T1 and T2, present an algorithm which computes their distance.

Example 1: Let T1 and T2 are the two trees illustrated at the beginning of this post. To convert the right tree to the left tree, one can build a tree of cost 3 on top of ×, and change 4 to 1 (the total cost is 4).

Example 2: Let T1=$$x^4$$ be represented by the following tree. To convert T1 to T2=$$x^4+4x^3+6x^2+4x+1$$, it suffices to add 1 to each of the $$x$$ nodes, to optain $$(x+1)^4$$=T2. This can be done by adding a cost-1 expression tree on top of each $$x$$ node. This example shows that the term-by-term conversion (which I called the greedy approach at the beginning of this post) is not an optimal approach. That is, if one wants to produce terms in T2 which are not present in T1 (i.e. $$4x^3$$, $$6x^2$$, $$4x$$, and 1), the cost will be much higher.

• If "delete" operation is not allowed, then the distance is not a distance. For example: a tree T1=(x*x)+4 cannot be transformed to T2=x, but T2 can be transformed to T1 adding (*x) and then (+4) on top of x. Is it ok ? Or you should define the distance as the minum operations required to convert T1 to T2 or T2 to T1. Commented Feb 6, 2011 at 11:43
• The cost is equal to 0 if and only if the two given (division-free) arithmetic formulas represent the same polynomial. If I remember it correctly, this is a typical problem in coRP (by random assignment) which is not known to be in P. Commented Feb 6, 2011 at 19:06
• @Tsuyoshi: Oh, I see. You're pointing at the polynomial identity testing problem. (Good references: [1] and [2]). I must think about this. Meanwhile, any suggestion is welcome. Commented Feb 6, 2011 at 19:56
• Yes, that’s it. It seems that in the typical version of the polynomial identity testing problem, two input polynomials are given as circuits, not formulas. So my wording that the formula version is “typical” was probably inaccurate. Anyway putting even the formula version in P seems to be an open problem. Commented Feb 6, 2011 at 20:08
• @Vor: In the current formulation, the input T1 is really a tree and the input T2 is a polynomial which just happens to be given as a tree, in the following sense. Changing T1 to a different tree which represents the same polynomial can change the answer in general, whereas changing T2 in a similar way does not. Commented Feb 7, 2011 at 2:08