Redução do espaço de log do stconn para ciclo

Question

Eu li este post: Mostrando ciclo é nl-completo?/ a>, mas não tenho certeza porque a redução é o espaço de log, pois requer acompanhar o novo gráfico, que tem $ n ^ 2 $ nós. .

Answer 1

Não há necessidade de armazenar o novo gráfico na fita.Nós só precisamos ser capazes de distribuí-lo no logspace.Isso é direto, por qualquer codificação razoável de gráficos.