# Show that the multiplication lies in FL

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?

• 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. – Uriel Dec 3 '12 at 21:04
• The same question was asked on math.stackexchange a while ago: math.stackexchange.com/questions/75770/… – Yuval Filmus Dec 4 '12 at 18:06
• @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. – Uriel Dec 4 '12 at 18:27
• @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? – Uriel Dec 4 '12 at 19:00
• @YuvalFilmus: I'm then wondering how the Turing machine can do the calculation. What is this information? – 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).

• 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). – Uriel Nov 29 '12 at 20:49
• 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. – Uriel Nov 30 '12 at 11:09
• 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? – Uriel Nov 30 '12 at 16:04
• 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? – Uriel Nov 30 '12 at 19:14
• 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. – 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)$

• Multiplication is complete for TC^0 and provably not in NC^0. – Kaveh Mar 1 '13 at 8:39
• It is not even in AC0. The paper proved equivalences under AC0 reductions not that they are in AC0. – Kaveh Mar 1 '13 at 17:35
• @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? – Ran G. Mar 2 '13 at 1:40
• I think I see the problem, nevermind that. – Ran G. Mar 2 '13 at 8:47