Reducción del espacio de registro de STCONN a CICLO

Question

Leí esta publicación: ¡Mostrar ciclo es NL-complete? , pero no estoy seguro de por qué la reducción es el espacio de registro, ya que requiere realizar un seguimiento del nuevo gráfico, que tiene $ n ^ 2 $ nodos.

Answer 1

No hay necesidad de almacenar el nuevo gráfico en la cinta.Solo necesitamos poder enviarlo en Logspace.Esto es sencillo, para cualquier codificación razonable de gráficos.