مبرهنة سافيتش: الفرق بين النسختين

فلتكن <math> L\in NSPACE(s(n))</math> لغة التي يمكن تقريرها بواسطة الة تيورنج غير قطعية , M , التي تستغل (s(n مساحة اضافية . لكل <math> x\in \{0,1\}^* </math> [[آلة تورنج#صورة الة تيورنج|مخطط الصُوَر]] , G=G_M,x , يوجد فيه على الاكثر <math> m=2^{s(n)} </math> رؤوس . لاحظ انَّ <math> x\in L </math> فقط اذا يوجد من الصورة الاولية , نرمز لها s , مسار موجه الىإلى الصورة النهائية , نرمز لها t , هذه المسألة تُعرف ايضا بمسألة الوصول وهي مسألة تقرير : معطى مخطط G , وكذلك رأسين s و-t ,قرر اذا ما يوجد مسار موجه بين s و- t . يمكن حل هذه المسألة بسهولة بواسطة DFS او BFS ولكن المساحة الاضافية المستخدمة خطية (اي <math>2^{O(s)}</math>) وهذا لا يفيد للمبرهنة .

# (Reach(u,v,i="نعم" <math> \iff</math> يوجد رأس z بحيث يمكن الوصول من u الىإلى z وطول المسار بينهما على الاكثر <math>2^{i-1}</math> , ويمكن الوصول من z الىإلى v حيث ان طول المسار بينهما على الاكثر <math>2^{i-1}</math> .