Сокращение журнала STCONN до цикла

Question

Я прочитал этот пост: Отображение цикла NL-Complete? , но я не уверен, почему уменьшение - это пространство журнала, так как требует отслеживания нового графа, который имеет $ n ^ 2 $ / P >.

Answer 1

Нет необходимости хранить новый граф на ленте.Нам просто нужно иметь возможность выводить его в logspace.Это просто, для любого разумного кодирования графов.