patternMinor
Show that the multiplication lies in FL
Viewed 0 times
showthemultiplicationliesthat
Problem
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?
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?
Solution
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).
Comment: Multiplication is actually in NC1 (hard) and even in TC0 (harder).
Context
StackExchange Computer Science Q#7022, answer score: 3
Revisions (0)
No revisions yet.