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?

  • 3
    $\begingroup$ In what model of computation? (e.g. circuits, TMs) $\endgroup$ – usul Sep 8 '13 at 12:58
  • $\begingroup$ I think for both circuits and TMs superlinear lower bound for multiplication is not known. $\endgroup$ – T.... Sep 8 '13 at 13:59
  • $\begingroup$ 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. $\endgroup$ – Markus Bläser Sep 9 '13 at 9:07

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?).

| cite | improve this answer | |

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.