2
$\begingroup$

In paper http://www.iro.umontreal.ca/~mckenzie/Recherche/homc10fun.pdf the authors prove their problem is NL-complete. At some point in their proof however, they construct a polynomial-sized graph, and state this can clearly be done in logspace, which is not that clear to me. It would seem to me that constructing a polynomial-sized graph would only be doable with polynomial space, since how would one store the constructed graph with less space? The wikipedia page on logspace reductions tries to clear up this misunderstanding by stating

It is possible that such a machine may not have space to write down its own output, so the only requirement is that any given bit of the output be computable in log-space.

which somewhat helps. I'm still missing the intuition behind it though, and am searching for an intuitive example of why the construction of some polynomial-sized structure can "clearly" be done in logspace.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.