An Improved Overlap Argument for On-line Multiplication

A lower bound of cN1ogN is proved for the mean time complexity of an on-line multitape Turing machine performing the multiplication of N-digit binary integers. For a more general class of machines the corresponding bound is cN1ogN. These bounds compare favorably with know upper bounds of the form c...

पूर्ण विवरण

ग्रंथसूची विवरण
मुख्य लेखकों: Paterson, Michael S., Fischer, Michael J., Meyer, Albert R.
प्रकाशित: 2023
ऑनलाइन पहुंच:https://hdl.handle.net/1721.1/148869