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?
-
$\begingroup$ 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)$)? $\endgroup$ – dkaeae May 29 '19 at 7:37
-
$\begingroup$ I'm sorry, my meaning was (log n)^c1. Thank you. $\endgroup$ – LioH May 29 '19 at 8:19
$\begingroup$
$\endgroup$
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.
