On complexity of arithmetic operations 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?
If integer multiplication is in linear time, then the Hartmanis-Stearns conjecture on real-time computation is false. See this post by Richard Lipton (and Ken Regan?).