I don't know exactly how to solve the exercise below.

Show that the multiplication lies in $\text{FL}$.

Hint: A useful approach to a solution is to split the exercise into two parts and to explain that each function lies in $\text{FL}$. The standard multiplication scheme can be used as an intermediate step. Example:

$\begin{align} 1001 \cdot{} 1100 & = \\ 1001000\\ + \ \ \ 100100\\ + \ \ \ \ \ \ \ \ \ \ \ \ 0\\ + \ \ \ \ \ \ \ \ \ \ \ \ 0\\ \end{align}$

Other useful approaches are certainly also accepted.

Useful definitions from our lecture notes:

Let $f : \Sigma^* \to \Sigma^*$ be a function, let $t : \mathbb N \to \mathbb N$ be a time bound and let $s : \mathbb N \to \mathbb N$ be a memory space bound.

$\bullet$ It is $f \in \text{FDTIME}(t),$ if there exists a DTM $M$ with an output tape, calculating $f$ and for which $T_M \in O(t)$ holds.

$\bullet$ It is $A \in \text{FDSPACE}(s),$ if there exists an offline DTM $M$, calculating $f$ and for which $S_M \in O(s)$ holds. The fields being written on the output band are not considered for the amount of memory space.

$\text{FP}=\bigcup_{k \in \mathbb N} \text{FDTIME}(n^k), \text{FL}=\text{FDSPACE}(\log n)$

I think the hint wants me to find two functions (one for the multiplication and one for the addition), but I don't see how to find two functions that do the calculation of the example in the appropriate way. Can somebody help me, please?

  • $\begingroup$ Can somebody else also write an answer, please? I still have difficulties with this exercise and it makes me very sad, because I've spent already several hours for it. $\endgroup$
    – Uriel
    Dec 3 '12 at 21:04
  • 1
    $\begingroup$ The same question was asked on math.stackexchange a while ago: math.stackexchange.com/questions/75770/… $\endgroup$ Dec 4 '12 at 18:06
  • $\begingroup$ @YuvalFilmus: Thanks for the link (or better: Toda), but the only answer there talks about the facts, not how to show them or even how to provide an appropriate solution for my exercise. I don't know, maybe the solution is 2 sides long and so nobody wants to write it down here in this thread. $\endgroup$
    – Uriel
    Dec 4 '12 at 18:27
  • $\begingroup$ @YuvalFilmus: So considering the example above, the input tape would contain $1001 \cdot{} 1100$, the work tape would contain the four summands with all carry and the output tape would contain the result? So far, so good but is this already an acceptable solution? $\endgroup$
    – Uriel
    Dec 4 '12 at 19:00
  • $\begingroup$ @YuvalFilmus: I'm then wondering how the Turing machine can do the calculation. What is this information? $\endgroup$
    – Uriel
    Dec 4 '12 at 20:52

Hint: Consider the standard multiplication scheme. Suppose that we compute the sum column by column, starting with the LSB. How big is the carry we have to remember?

Comment: Multiplication is actually in NC1 (hard) and even in TC0 (harder).

  • $\begingroup$ Thanks for your answer. The carry has always the size 1. But to be honest I fail to take the hint; maybe my way of thinking is too complicated... NC and TC haven't been introduced in the lecture so far (I've heard them for the first time). $\endgroup$
    – Uriel
    Nov 29 '12 at 20:49
  • $\begingroup$ In the example four rows of bits are added. But I really don't know, why the carry doesn't have size 1. I mean if for example 1+1 then I write 0 and remember 1; if 1+0 then I write 1 and there is no carry. $\endgroup$
    – Uriel
    Nov 30 '12 at 11:09
  • $\begingroup$ For example 1111+1111=11110 and this addition has 4 carry digits. So the total number of carry digits depends on the length of the binary (worst case). Is this what you mean? $\endgroup$
    – Uriel
    Nov 30 '12 at 16:04
  • $\begingroup$ Now I see that the carry can grow dramatically. But how do I determine the general case and how does this help me to solve the exercise? $\endgroup$
    – Uriel
    Nov 30 '12 at 19:14
  • $\begingroup$ I don't know if you get notified when there is a message in chat, but if you could have a look into it or give some further help in this thread, it would be much appreciated, since I still have difficulties. $\endgroup$
    – Uriel
    Dec 4 '12 at 15:47

Wikipedia gives great information about the complexity of various elementary operations.

Multiplication takes $n^2$ time by the "school-book" algorithm, and thus it is in $\mathsf{FTIME}(n^2)$ and in $\mathsf{FL}$. Better solutions exist.

Also, it's quite simple to see that all you need is 3 registers of size $2\log n$, to complete the schoolbook algorithm, so the problem is $\mathsf{FSPACE}(\log n)$

  • $\begingroup$ Multiplication is complete for TC^0 and provably not in NC^0. $\endgroup$
    – Kaveh
    Mar 1 '13 at 8:39
  • $\begingroup$ It is not even in AC0. The paper proved equivalences under AC0 reductions not that they are in AC0. $\endgroup$
    – Kaveh
    Mar 1 '13 at 17:35
  • $\begingroup$ @kaveh, I must be missing something, but their Thm3.1 along with Prop2.1 (part 3) makes all the problem they show there in $AC^0$, not? $\endgroup$
    – Ran G.
    Mar 2 '13 at 1:40
  • $\begingroup$ I think I see the problem, nevermind that. $\endgroup$
    – Ran G.
    Mar 2 '13 at 8:47

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.