Is this strange problem NP-complete? - MathOverflow

Is this strange problem NP-complete?

2010-05-15T17:16:25Z

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?

Answer by supercooldave for Is this strange problem NP-complete?

2010-05-15T17:21:55Z

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)$.

Answer by Tony Huynh for Is this strange problem NP-complete?

2010-05-15T21:33:25Z

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.

Answer by Gerhard Paseman for Is this strange problem NP-complete?

2010-05-18T00:22:40Z

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