Riduzione dello spazio del registro da STCONN al ciclo

Question

Ho letto questo post: Mostra il ciclo è completo? , ma non sono sicuro del motivo per cui la riduzione è lo spazio del registro, in quanto richiede la tenuta del nuovo grafico, che ha $ n ^ 2 $ nodi. .

Answer 1

Non è necessario memorizzare il nuovo grafico sul nastro.Dobbiamo solo essere in grado di emetterlo nel logspace.Questo è semplice, per qualsiasi codifica ragionevole dei grafici.