The best upper bound known on the time complexity of multiplication is Martin Fürer's bound $n\log n2^{O(\log^* n)}$, which is more than linear time complexity of addition. Do we have a proof that addition is inherently easier than multiplication?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Corrected the time bound. $\endgroup$– JeffεSep 20, 2012 at 21:26
-
1$\begingroup$ see also major unsolved problems in TCS $\endgroup$– vznSep 20, 2012 at 23:35
-
1$\begingroup$ it is going to depend on how you represent your numbers; if you deal with the log of the number multiplication is faster that addition (as it requires a pow and a log) $\endgroup$– ratchet freakSep 20, 2012 at 23:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
No.
No unconditional better lower bound than the trivial $\Omega(n)$ is currently known for integer multiplication. There are some conditional lower bounds though. For more on this, you can have a look at Martin Fürer's paper Faster Integer Multiplication.
Edit following Andrej's comment: Addition can be done in time $\mathcal O(n)$. In comparison, the best known upper bound for multiplication is (approximately) $\mathcal O(n\log n)$. On the other hand, no non trivial lower bound is known for multiplication, thus there is no proof that addition is faster than multiplication yet. As (too) often in complexity theory, we just don't know!
-
$\begingroup$ It seems to me that the paper doesn't disprove that the addition is faster than multiplication. Should I assume that there is no proof for that yet? $\endgroup$– HoomanSep 20, 2012 at 20:04
-
8$\begingroup$ What Bruno is saying is this: clearly we can do addition in linear time, and we cannot do it faster than in linear time (because you have to look at the input). Therefore, showing that addition is harder than multiplication is the same thing as showing that multiplication cannot be done in linear time. But there is no such proof. $\endgroup$ Sep 20, 2012 at 20:38
-
2$\begingroup$ @andrej you mean "showing multiplication is harder than addition" right? the poster got it mixed up also on an earlier version of the question. also quibble, there is no such proof known. this also seems like a good candidate for mathoverflow, "most 'obvious' open problems in complexity theory" $\endgroup$– vznSep 20, 2012 at 23:27
-
$\begingroup$ @vzn it's a great answer to that MO question, IMO. $\endgroup$ Sep 21, 2012 at 3:49
-
$\begingroup$ @SashoNikolov I'm not sure - I don't know if multiplication being in O(n) would be all that shocking. Certainly a surprise, but AFAIK there's no good reason except by analogy with problems like sorting, Fourier transforms, etc. to believe that the 'naturally' O(n^2) multiplication problem couldn't be simplified all the way down to linear time. $\endgroup$ Sep 24, 2012 at 21:06