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
    Commented Dec 3, 2012 at 21:04
  • 1
    $\begingroup$ The same question was asked on math.stackexchange a while ago: math.stackexchange.com/questions/75770/… $\endgroup$ Commented Dec 4, 2012 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
    Commented Dec 4, 2012 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
    Commented Dec 4, 2012 at 19:00
  • $\begingroup$ @YuvalFilmus: I'm then wondering how the Turing machine can do the calculation. What is this information? $\endgroup$
    – Uriel
    Commented Dec 4, 2012 at 20:52

2 Answers 2


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
    Commented Nov 29, 2012 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
    Commented Nov 30, 2012 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
    Commented Nov 30, 2012 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
    Commented Nov 30, 2012 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
    Commented Dec 4, 2012 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
    Commented Mar 1, 2013 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
    Commented Mar 1, 2013 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.
    Commented Mar 2, 2013 at 1:40
  • $\begingroup$ I think I see the problem, nevermind that. $\endgroup$
    – Ran G.
    Commented Mar 2, 2013 at 8:47

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.