Log space reduction from STCONN to CYCLE
-
29-09-2020 - |
Question
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.
Solution
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.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange