1
$\begingroup$

I read this post: Showing Cycle is NL-complete?, but I am not sure why the reduction is log space, as it requires keeping track of the new graph, which has $n^2$ nodes.

$\endgroup$
  • $\begingroup$ The new graph has $O(n^2)$ nodes. $\endgroup$ – Yuval Filmus May 21 at 20:36
  • $\begingroup$ Thank you for correction. However, I am still not sure why it is a log space reduction. $\endgroup$ – Quin Morris May 21 at 20:37
1
$\begingroup$

There is no need to store the new graph on the tape. We just need to be able to output it in logspace. This is straightforward, for any reasonable encoding of graphs.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How can the new graph computed in log space? $\endgroup$ – Quin Morris May 21 at 20:50
  • $\begingroup$ As I said, it's straightforward, assuming you understand logspace computation well enough. There's no point in me spelling it out. All you have to do is be able to write a description of the new graph. You can do this using a few loops, with all loop variables being of logarithmic size (and linear or quadratic magnitude). $\endgroup$ – Yuval Filmus May 21 at 20:52

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.