20
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Feb 6 '11 at 11:43
  • 4
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Feb 6 '11 at 19:06
  • 4
    $\begingroup$ @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. $\endgroup$ – M.S. Dousti Feb 6 '11 at 19:56
  • 4
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Feb 6 '11 at 20:08
  • 2
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Feb 7 '11 at 2:08
10
$\begingroup$

Tree Edit Distance is a generalization of string edit distance. The distance between two trees is the minimum number of node insertions \ deletions \ and relabels required to turn one tree into the other. (when we delete node v, v's children become children of parent(v)). The problem is NP-hard when the trees are unordered, but when they are ordered (i.e., there is a left-to-right order among siblings) the problem is solvable in O(n^3) time (as in the paper that Sadeq mentioned). A good survey that describes this: http://portal.acm.org/citation.cfm?id=1085283

$\endgroup$
  • 1
    $\begingroup$ Thanks Aviv. It will be great if you merge your responses (I think you have issues using your previous account). You can use the advices in this post (Specially, this link). $\endgroup$ – M.S. Dousti Feb 7 '11 at 12:49
  • $\begingroup$ How would this approach cover different trees with eqivalent polynomials $\endgroup$ – narek Bojikian Jan 12 at 3:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.