# Log-space reduction - How to calculate overall space needed?

Assume A, B are two decision problems. Given a reduction from A to B that uses log^c1(n) space and an algorithm that solves B in log^c2(n) space, Can we determine some lower bound to the space needed by an algorithm which solves A using this reduction?

• How is $\log^{c_1}(n)$ defined? Is it $(\log n)^{c_1}$ or $\log$ composed with itself $c_1$ times (i.e., $(\log \circ \log \circ \cdots)(n)$)? – dkaeae May 29 at 7:37
• I'm sorry, my meaning was (log n)^c1. Thank you. – LioH May 29 at 8:19

The answer depends on how large the output of the reduction $$f$$ is. Usually, in the context of log-space reductions, there are two main variants of composing reductions (or, in this case, composing a reduction with an algorithm solving the reduced problem directly). Goldreich ("Computational Complexity: A Conceptual Perspective") names these naive and emulative compositions, though I don't believe there is a widely agreed terminology for them. (Please correct me if I'm wrong.)
Let $$x$$ denote a problem instance of $$A$$.
Naive composition. If $$|f(x)|$$ is small, then we can compute the entirety of $$f(x)$$ and then apply the algorithm solving $$B$$, reusing the space used to compute $$f$$. This means the space complexity is on the order of $$\max(\log(|x|)^{c_1}, \log(|f(x)|)^{c_2}) + |f(x)|$$ plus some minor factors to organize things (e.g., keep track of whether we are performing the reduction or running the algorithm solving $$B$$).
Emulative composition. If $$|f(x)|$$ is large, then it makes sense not to generate the entirety of it in a single batch but, rather, to generate it bit-by-bit on the fly (i.e., as the algorithm solving $$B$$ needs it). Hence, whenever the algorithm solving $$B$$ needs bit number $$i$$ of $$f(x)$$, we run the reduction from scratch up to the point where bit number $$i$$ is produced and then pass this over to $$B$$. This means $$f(x)$$ is a virtual value which we provide to the algorithm for $$B$$ only on a bit-by-bit basis. Reusing space like this gives a space complexity on the order of $$\log(|x|)^{c_1} + \log(|f(x)|)^{c_2} + O(\log(|f(x)|))$$ plus some minor factors, as before (e.g., to keep track of what bit of $$f(x)$$ we have last provided). Note how this is a big improvement whenever $$|f(x)|$$ is large.