# Is there a proof that addition is faster than multiplication?

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?

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

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!