I can prove this if I use a NTM Turing Machine, but it is required to use a two-taped DTM, while taking into account only the space of the second "work tape"

  • $\begingroup$ Can you provide an outline of how you would handle this using the NTM and where you get stuck moving to the DTM? Questions with context and shown-working tend to be better received and answered. $\endgroup$ – postmortes Jan 11 at 12:40
  • $\begingroup$ When you say "NTM Turing Machine", does that mean "Non-deterministic Turing Machine Turing Machine"? $\endgroup$ – Arthur Jan 11 at 13:44
  • $\begingroup$ Refer to the section titled 'Optimizing Space Complexity' in the link en.wikipedia.org/wiki/Multiplication_algorithm. $\endgroup$ – user137481 Jan 15 at 23:40

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.