<p>If integer multiplication is in linear time, then the Hartmanis-Stearns conjecture on real-time computation is false. See <a href="https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/" rel="nofollow">this post</a> by Richard Lipton (and Ken Regan?).</p>

CC BY-SA 3.0
2013-09-08T14:12:47.297Z
2013-09-08T14:12:47.297Z
Joshua Grochow
<p>Though there have been many questions asked in this forum on complexity of integer operation, I could not find an answer to the following question: What implications are there to complexity theory if integer addition and multiplication of two integers have the same asymptotic complexity in the worst case?</p>

CC BY-SA 3.0
2013-09-08T12:58:12.183Z
In what model of computation? (e.g. circuits, TMs)
usul
CC BY-SA 3.0
2013-09-08T13:59:14.023Z
I think for both circuits and TMs superlinear lower bound for multiplication is not known.
Turbo
CC BY-SA 3.0
2013-09-09T09:07:05.493Z
There are models where multiplication can be done in linear time, e.g., pointer machines. A. Schönhage, SIAM J. Comput., 9(3), 490–508.
Markus Bläser
<cc.complexity-theory>
On complexity of arithmetic operations
Turbo
# On complexity of arithmetic operations

(Asked by: username_0 on 2013-09-08)

Though there have been many questions asked in this forum on complexity of integer operation, I could not find an answer to the following question: What implications are there to complexity theory if integer addition and multiplication of two integers have the same asymptotic complexity in the worst case?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: In what model of computation? (e.g. circuits, TMs)  
> **username_0**: I think for both circuits and TMs superlinear lower bound for multiplication is not known.  
> **username_2**: There are models where multiplication can be done in linear time, e.g., pointer machines. A. Schönhage, SIAM J. Comput., 9(3), 490–508.  

---

## 1 answers

### Answer by username_3 on 2013-09-08. Score: 3 | Accepted answer

If integer multiplication is in linear time, then the Hartmanis-Stearns conjecture on real-time computation is false. See [this post](https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/) by Richard Lipton (and Ken Regan?).


---

