<h2>No.</h2>

<p>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 <a href="http://www.cse.psu.edu/~furer/Papers/mult.pdf"><em>Faster Integer Multiplication</em></a>.</p>

<p>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!</p>

CC BY-SA 3.0
2012-09-20T20:04:19.877Z
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?
Hooman
CC BY-SA 3.0
2012-09-20T20:38:50.767Z
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.
Andrej Bauer
CC BY-SA 3.0
2012-09-20T23:27:35.910Z
@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"](http://mathoverflow.net/questions/35422/most-obvious-open-problems-in-complexity-theory)
vzn
CC BY-SA 3.0
2012-09-21T03:49:13.783Z
@vzn it's a great answer to that MO question, IMO.
Sasho Nikolov
CC BY-SA 3.0
2012-09-24T21:06:18.793Z
@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.
Steven Stadnicki
CC BY-SA 3.0
2012-09-20T19:58:45.180Z
2012-09-22T19:46:50.373Z
2012-09-22T19:46:50.373Z
Bruno
<p>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? </p>

CC BY-SA 3.0
2012-09-20T21:26:46.033Z
Corrected the time bound.
Jeffε
CC BY-SA 3.0
2012-09-20T23:35:53.617Z
see also [major unsolved problems in TCS](http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science)
vzn
CC BY-SA 3.0
2012-09-20T23:42:33.710Z
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
<cc.complexity-theory><time-complexity>
Is there a proof that addition is faster than multiplication?
Hooman
# Is there a proof that addition is faster than multiplication?

(Asked by: username_0 on 2012-09-20)

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?

**Tags:** cc.complexity-theory, time-complexity

> **Comments:**
> **username_1**: Corrected the time bound.  
> **username_2**: see also [major unsolved problems in TCS](http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science)  
> **username_3**: 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)  

---

## 1 answers

### Answer by username_4 on 2012-09-20. Score: 31 | Accepted answer

## 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*](http://www.cse.psu.edu/~furer/Papers/mult.pdf).

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!

> **Comments:**
> **username_0**: 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?  
> **username_5**: What username_4 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.  
> **username_2**: @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"](http://mathoverflow.net/questions/35422/most-obvious-open-problems-in-complexity-theory)  
> **username_6**: @username_2 it's a great answer to that MO question, IMO.  
> **username_7**: @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.  

---

