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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.