15
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ I disagree that the $2x$ factor is irrelevant: $2x(2x - 1) - 2x(x + 2) = 2x(x - 3)$. $(x + 1)(x - 3) + 2x(x - 3) - (3x + 1)(x - 3) = 0$. But maybe this is just a coincidence of this example, and there really are examples where there are "irrelevant factors" such that combining them leads to a dead-end. $\endgroup$
    – JBL
    Commented May 15, 2010 at 17:37
  • $\begingroup$ I actually checked that statement, but what you write demonstrates that my check came to the wrong conclusion. I'm fairly sure, but not certain, that irrelevant common factors can exist. $\endgroup$
    – gowers
    Commented May 15, 2010 at 17:46
  • 5
    $\begingroup$ The $x+4$ factors are irrelevant in (x+1)(x+2) + (x+2)(x+4) + (x+4)(2x+5), I think. $\endgroup$
    – Tom Smith
    Commented May 15, 2010 at 21:30
  • $\begingroup$ Maybe the question should be asked in a more abstract way as computing the result can be done in a fast way. I am thinking something like we want to compute the sum of n instances of a symmetric bilinear function over a vector space but we can access this function only through queries and we want to ask as few queries as we can. Gowers even gives us the promise that there is a way to ask only one query. Can we make the computation in P with one query or is it NP-hard to do it? $\endgroup$
    – domotorp
    Commented May 16, 2010 at 9:39
  • $\begingroup$ Do you allow simplifications like (x+1)(x+2)+(x+1)(x-3)+(x-5)(x+3)+(x-5)(x-4)=(x+1)(2x-1)+(x-5)(2x-1)=(2x-4)(2x-1), where the you cannot alway use the term you got in the last simplification to simplify further? Your remark about "simple path" could suggest that this is not allowed, since this is more like a tree. $\endgroup$
    – Sune Jakobsen
    Commented May 18, 2010 at 14:14

3 Answers 3

Reset to default
4
$\begingroup$

Here's an idea (not a solution), which I thought I would post before heading out for coffee inspiration.

Let $f(x)=\sum_{i=1}^n p_i(x)$ be the expression we are attempting to simplify. One possible approach is to ask which $p_i$ can be the last polynomial of the simplification. To answer this, we can first use the $O(nlog(n))$ algorithm to compute the factorization of $f$. Say $f(x)=(ax+b)(cx+d)$. Then, the only possible choices for the last polynomial are the $p_i$'s that are divisible by $(ax+b)$ or $(cx+d)$. If we are lucky, there might only be one such choice, say $p_k$. We can then replace $f$ by $f-p_k$ and recurse. This approach will certainly work in the case that there is a unique ordering of simplification.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I had the same idea, but isn't there also a danger of there being irrelevant factors as in the comments? $\endgroup$
    – Qiaochu Yuan
    Commented May 17, 2010 at 3:53
  • $\begingroup$ Yes, proceeding backwards instead of forwards has its perils as well. That is, if there is more than one $p_i$ which has a common factor with $f$, then it is not clear which $p_i$ is last. Let's compare going forwards to going backwards. If there are only two $p_i$ which have a common factor, then they must be the first two polynomials of the simplification. If there is exactly one polynomial which has a common factor with the entire sum, then it must be the last polynomial of the simplification. Perhaps a clever combination of the two techniques can be used, but I don't see it. $\endgroup$
    – Tony Huynh
    Commented May 17, 2010 at 7:38
2
$\begingroup$

I imagine the obvious algorithm is the most clever one. If it is a quadratic, then the time complexity is presumably at most $O(n^2)$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ What is the obvious algorithm? The only obvious algorithm I can see appears to take exponential time. $\endgroup$
    – gowers
    Commented May 15, 2010 at 17:23
  • $\begingroup$ Expand out the terms and then calculate the roots using $\frac{-b\pm\sqrt{b^2-4ac}}{2a}$ en.wikipedia.org/wiki/Quadratic_equation . Or perhaps don't understand your question. What are you aiming for? What is your criteria for stopping the search you allude to? $\endgroup$
    – supercooldave
    Commented May 15, 2010 at 17:56
  • $\begingroup$ I think supercooldave is right, except that the obvious algorithm looks linear to me. If each summand of the input can only be of the form $(ax+b)(cx+d)$, then reducing each summand to the form $acx^2 + (bc+ad)x + bd$ will take constant time, and then reducing $n$ summands to a quadratic will take $O(n)$ time, as will adding up the coefficients. Then you can apply the quadratic equation and you're done. $\endgroup$
    – Neel Krishnaswami
    Commented May 15, 2010 at 18:14
  • 3
    $\begingroup$ No, he doesn't want the final solution. He (she) wants to reduce the expression, by taking two terms together, when the two terms have one part in common. He wants to know whether the final solution can be reached, by doing this repeatedly. In fact you the whole expression thing is not so relevant. If you have n pairs, you may do the following: I) swap (a,b) in (b,a) or II) reduce two pairs (a,b) and (a,c) into (a,(b+c)/2) The question is, whether the n pairs can be reduced to one. $\endgroup$
    – Lucas K.
    Commented May 15, 2010 at 18:26
  • 2
    $\begingroup$ Lucas K., that is how I understand the question as well, except that (b + c)/2 should just be (b + c) in your penultimate sentence. (Actually, I guess there are two similar but different approaches, one in which we always have monic factors (and pull the leading coefficient in front) and the other in which we aren't allowed to make such a simplification, i.e., for which x(2x - 2) + (x + 1)(x - 1) is a dead end.) $\endgroup$
    – JBL
    Commented May 15, 2010 at 18:40
0
$\begingroup$

Here is a different idea, also not a solution. The difference between 2-SAT and 3-SAT is that in 2-SAT, the clauses can be arranged into a series (or tree) of implications which can be resolved, and thus a satisfying variable assignment to each of the 2-variable clauses can be found quickly. I am thinking that there is a connection between the coefficients and boolean variables indexed by the coefficients that will result in a nice reduction. I further prognosticate that trying something similar for cubics will suffer the same speed blocks as does 3-SAT.

Of course, I've guessed wrong before.

Gerhard "Ask Me About System Design" Paseman, 2010.05.17

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .