The following quadratic expression can be simplified:
(x+1)(x+2) + (x+1)(x-3) + 2x(2x-1) - (3x+1)(x-3) - 2x(x+2).
What is the easiest way of doing the simplification? (It would be good to think about this for a few seconds before continuing.)
A natural instant reaction is to think that the best thing to do is probably to expand out all the brackets, collect all the terms into a single quadratic written in the form ax^2 + bx +c, and then to factorize it if it has a nice factorization. (I'm quite interested to know how typical this reaction is.)
However, it is noticeable that the first two terms have a common factor x+1. Is this of any help? It is not all that promising that later terms do not have this factor, but if out of curiosity one adds the other two factors x+2 and x-3 together, one gets 2x-1, which occurs in the third term. If one spots that, then it is a short step to spotting that the expression has been concocted in such a way that the process continues. So in fact one can simplify the whole thing in one's head quite easily, and it even ends up nicely factorized.
My question is this. Suppose you produced an example made out of n terms of the above form, and then permuted it. Is there a good algorithm for finding a "simple path" from term to term that allows you to keep combining two terms into one without ever expanding out the brackets? To put it another way, if I concocted a very long example and then permuted it, is there a nice algorithm for demonstrating that it is an example? The catch is that there may well be plenty of irrelevant common factors (just as the common factor of 2x between the third and fifth terms above did not play a role), so there is no uniqueness about the next step to take. A depth-first search would lead to unacceptable amounts of backtracking. So is the problem NP-complete, or is there a clever algorithm?