مبرهنة سافيتش

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

نعرف (Reach(u,v,i على انه "نعم" إذا يوجد مسار بين u و- v طوله على الأكثر 2ⁱ و"لا" خلاف هذا . لاحظ انه :

1. ((Reach(s,t,log(n = "نعم" فقط إذا يوجد مسار بين s و- t . (اي انه يمكننا حل مسألة الوصول)
2. (Reach(u,v,i="نعم" ${\displaystyle \iff }$ يوجد رأس z بحيث يمكن الوصول من u إلى z وطول المسار بينهما على الأكثر ${\displaystyle 2^{i-1}}$ , ويمكن الوصول من z إلى v حيث ان طول المسار بينهما على الأكثر ${\displaystyle 2^{i-1}}$ .

بواسطة هذه الملاحظات امكن ان نحصل على خوارزمية عودية والتي مساحتها الاضافية التي تستخدمها على الأكثر هي ${\displaystyle O(s^{2}(n))}$ .

def k_edge_path(s, t, k):
    if k == 0:
        return s == t
    else if k == 1:
        return s == t or (s, t) in edges
    else:
        for u in vertices:
            if k_edge_path(s, u, floor(k / 2)) and k_edge_path(u, t, ceil(k / 2)):
                return true
    return false

• PSPACE=NPSPACE , وهذا لان تربيع كثير الحدود هو أيضا كثير حدود .
• NL⊆L² حيث أنَّ ((L²=SPACE(log²(n , وهذا ينبع من المبرهنة مباشرة، وكذلك لان مسألة الوصول هي مسألة كاملة في الصنف NL .

• مبرهنة اميرمان-زليبتسيني
• بيسبايس

• بوابة علم الحاسوب