Сокращение журнала STCONN до цикла
-
29-09-2020 - |
Вопрос
Я прочитал этот пост: Отображение цикла NL-Complete? , но я не уверен, почему уменьшение - это пространство журнала, так как требует отслеживания нового графа, который имеет $ n ^ 2 $ / P >.
Решение
Нет необходимости хранить новый граф на ленте.Нам просто нужно иметь возможность выводить его в logspace.Это просто, для любого разумного кодирования графов.
Не связан с cs.stackexchange