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

فلتكن ${\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 .

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

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