1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.