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.

Improve this question
$\endgroup$
1
  • $\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
    Commented Feb 4, 2018 at 22:21

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Feb 5, 2018 at 1:24

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.