سجل تخفيض المساحة من STCONN إلى دورة

Question

قرأت هذا المنشور: عرض دورة غير ملائمة؟ ، لكنني لست متأكدا من السبب في أن التخفيض هو تسجيل المساحة، لأنه يتطلب تتبع الرسم البياني الجديد، الذي يحتوي على $ n ^ 2 $ العقد.

Answer 1

ليست هناك حاجة لتخزين الرسم البياني الجديد على الشريط.نحن بحاجة فقط إلى أن نكون قادرين على إخراجها في Logspace.هذا واضح ومباشر، لأي ترميز معقول للرسوم البيانية.