Réduction de l'espace journal de stconn pour faire du vélo

Question

J'ai lu ce message: montrant le cycle est NL-complet? , mais je ne suis pas sûr de savoir pourquoi la réduction est l'espace de journal, car il nécessite de garder une trace du nouveau graphique, qui a $ n ^ 2 $ nœuds.

Answer 1

Il n'est pas nécessaire de stocker le nouveau graphique sur la bande.Nous devons juste être capable de le sortir dans Logspace.Ceci est simple, pour tout codage raisonnable des graphiques.