1
$\begingroup$

Given algebraic expression of two variables x and y, I want to simplify this algebraic expression until it cannot be simplified anymore. What algorithm can I use for this?

For instance:

x+x+y+y = 2•x+2•y = 2•(x+y)

x•x+y•y=x2+y2

(x+y)•(x+y)=(x+y)2

x•x+x•y+x•y+y•y=x2+2•x•y+y2=(x+y)2

The most simplified algebraic expression is the one with the fewest characters. Expressions will have only addition, multiplication, and exponentiation with a constant.

What is the complexity of this problem?

Does exist polynomial time and space algorithm to solve this problem? I tried to find over the Internet the algorithm to simplify algebraic expressions, but I didn't find anything. The problem is that I don't know where to start.

$\endgroup$
1
$\begingroup$

Minimizing the number of characters is a tough one.

The field of symbolic computation might be relevant, but I don't know of any algorithms that find a simplified form with the fewest characters.

Here's one approach you can use, that won't be optimal. Express the expression as a polynomial over variables $x,y$. Then, factor the polynomial. Computer algebra systems will include algorithms to do that for you. For the size problems you are talking about, this should be very efficient.

This won't necessarily find the optimal expression. For instance, $x^2 + y^2 + 2xy + 1$ is irreducible (can't be factored), but there is a shorter equivalent expression, namely $(x+y)^2 + 1$. However, in many cases it will find a way to simplify the expression to some extent.

Another approach, which also isn't optimal, is to use a template-based method. Suppose you have a "template" for what you expect the simplified expression might look like: e.g., you are interested in expressions of the form

$$T(x,y) = \sum_{j,k} a_{j,k} (b_{j,k} x + c_{j,k} y)^k + \sum_{j,k} d_{j,k} x^j y^k.$$

Then given an expression $f(x,y)$, it is possible to determine whether there is an equivalent expression of the form above. In particular, pick many random values $(x_i,y_i)$, evaluate the expression $f$ at each of those values, and set up one equation per value

$$f(x_i,y_i) = T(x_i,y_i).$$

Here since we can evaluate $f(x_i,y_i)$, the left-hand side of each such equation is a constant. Expanding out the definition of $T(x_i,y_i)$, the right-hand side is an expression in the unknowns $a_{j,k},b_{j,k},c_{j,k},d_{j,k}$. Thus, each value $(x_i,y_i) we pick gives us one equation on those unknowns. After sufficiently many equations, it should be possible to solve that system of (nonlinear) equations for the unknowns. (Computer algebra packages typically also include methods to solve a system of nonlinear equations for you.) There may be many solutions, in which case you could enumerate all solutions, or consider simpler templates and find one solution per template.

This might give you multiple candidates for simplified expressions, and you can keep the one that has the fewest characters. Again, there will be cases where it is not the optimal solution, but it might be useful for small expressions.

Finally, if you care about optimality more than efficiency, you could enumerate all expressions in order of increasing length, and test each one to see if it is equivalent to the original expression. A simple way to test whether two expressions are equivalent are to evaluate them at some randomly selected points; this is fast, but might occasionally err on the side of failing to realize that two inequivalent expressions are inequivalent. A more comprehensive test is to convert both expressions to polynomials, then check that their coefficients are equal. This should give the optimal solution, but I expect it will be inefficient: the running time is exponential in the length of the solution.

$\endgroup$
  • $\begingroup$ I won't to avoid exponential time and space as much as possible. $\endgroup$ – Farewell Stack Exchange Jul 12 '17 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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