Is this strange problem NP-complete? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T17:17:18Z http://mathoverflow.net/feeds/question/24782 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24782/is-this-strange-problem-np-complete Is this strange problem NP-complete? gowers 2010-05-15T17:16:25Z 2010-05-18T00:22:40Z <p>The following quadratic expression can be simplified:</p> <p>(x+1)(x+2) + (x+1)(x-3) + 2x(2x-1) - (3x+1)(x-3) - 2x(x+2).</p> <p>What is the easiest way of doing the simplification? (It would be good to think about this for a few seconds before continuing.) </p> <p>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.)</p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/24782/is-this-strange-problem-np-complete/24785#24785 Answer by supercooldave for Is this strange problem NP-complete? supercooldave 2010-05-15T17:21:55Z 2010-05-15T17:21:55Z <p>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)$. </p> http://mathoverflow.net/questions/24782/is-this-strange-problem-np-complete/24821#24821 Answer by Tony Huynh for Is this strange problem NP-complete? Tony Huynh 2010-05-15T21:33:25Z 2010-05-17T23:59:48Z <p>Here's an idea (not a solution), which I thought I would post before heading out for coffee inspiration. </p> <p>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 <em>last</em> 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. </p> http://mathoverflow.net/questions/24782/is-this-strange-problem-np-complete/25073#25073 Answer by Gerhard Paseman for Is this strange problem NP-complete? Gerhard Paseman 2010-05-18T00:22:40Z 2010-05-18T00:22:40Z <p>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.</p> <p>Of course, I've guessed wrong before.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.05.17</p>