5
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.