stconn에서 순환까지의 공간 축소를 기록합니다

Question

이 게시물을 읽었습니다. 주기가 NL-Complete입니까? 그러나 $ n ^ 2 $ 노드가있는 새 그래프를 추적 해야하는 이유는 로그 공간이되는지 모르겠습니다.

Answer 1

새 그래프를 테이프에 저장할 필요가 없습니다.우리는 단지 로그 공간에서 출력 할 수 있어야합니다.이것은 그래프의 모든 합리적인 인코딩에 대해 간단합니다.