1
$\begingroup$

Let MULT$=\{a\#b\#c| a,b,c \text{ binary natural numbers and } a\times b=c\}$

Prove that MULT $\in L$

How do I show that this language, MULT, is computable in Logarithmic space?

Let us assume a#b#c is on the input tape, we now need away of multiplying a with b and checking if the product is c, while using only $log(n)$ space while n is the length of the input.

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 4 '18 at 22:21
1
$\begingroup$

In high-school multiplication, you multiply $a$ by $b$ by summing shifted copies of $b$, some of them zeroed out (according to $a$). You can implement this algorithm in logspace by calculating the result from LSB to MSB, keeping track of the carry. The crucial point is that the carry is only $O(\log n)$ bits long.

$\endgroup$
  • $\begingroup$ What you call high school multiplication is the actual dirty work everybody tries to avoid in such questions, to write bit by bit depending on the bits order and if both the bits are 1 or 0 or if they are different. And it is where one is most likely to make a mistake. And it is exactly where I'd hoped to get some help. But all in all, you are right on the money.The high level description of the process is just what you gave in your respond. I only hope that if I give same sort of a high description in the exam without mimicking the whole process bit by bit, I hope then I don't loose points. $\endgroup$ – Anwar Saiah Feb 5 '18 at 1:24

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.