Timeline for Is this strange problem NP-complete?
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2010 at 14:14 | comment | added | Sune Jakobsen | 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. | |
| May 18, 2010 at 0:22 | answer | added | Gerhard Paseman | timeline score: 0 | |
| May 16, 2010 at 9:39 | comment | added | domotorp | 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? | |
| May 15, 2010 at 21:33 | answer | added | Tony Huynh | timeline score: 4 | |
| May 15, 2010 at 21:30 | comment | added | Tom Smith | The $x+4$ factors are irrelevant in (x+1)(x+2) + (x+2)(x+4) + (x+4)(2x+5), I think. | |
| May 15, 2010 at 17:46 | comment | added | gowers | 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. | |
| May 15, 2010 at 17:37 | comment | added | JBL | 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. | |
| May 15, 2010 at 17:21 | answer | added | supercooldave | timeline score: 2 | |
| May 15, 2010 at 17:16 | history | asked | gowers | CC BY-SA 2.5 |