Hi All!.

I have a following problem:

It is given two arithmetic expressions, operations - +, -, *, /, (), operands - just standard identifiers.
The question is: whether it is possible to rename identifiers and to rearrange operands at commutative operations (+, *) so that to reduce one expression to another.

For example:
1.
Input:
A+B
C+B
Output:
Yes

2.
Input:
(A+B-C)*(C+C)
(D+D)*(B+A-D)
Output:
Yes

3.
Input:
(A+A)+B
(A+B)+A
Output:
No

I found the (http://escholarship.org/uc/item/58v124c7) "Expression equivalence checking using interval analysis" article, but that algorithm requires defined intervals for identifiers values (and it does not allow the infinity value).
My algorithm is O(n^2) (please note this problem is NP-Hard), and i want to find a more efficient solution.

Does another (standard) algorithm exist for this problem? Or, may be, this problem can be reduced to another well-known problem?

Thank you.