21
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Corrected the time bound. $\endgroup$ – Jeffε Sep 20 '12 at 21:26
  • 1
    $\begingroup$ see also major unsolved problems in TCS $\endgroup$ – vzn Sep 20 '12 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 freak Sep 20 '12 at 23:42
30
$\begingroup$

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!

$\endgroup$
  • $\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$ – Hooman Sep 20 '12 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$ – Andrej Bauer Sep 20 '12 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$ – vzn Sep 20 '12 at 23:27
  • $\begingroup$ @vzn it's a great answer to that MO question, IMO. $\endgroup$ – Sasho Nikolov Sep 21 '12 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$ – Steven Stadnicki Sep 24 '12 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.