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

في نظرية التعقيد الحسابي مبرهنة سافيتش هي نتيجة أساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي. ونص المبرهنة هو:

$\forall s(n)>log(n){\mbox{ }},{\mbox{ }}NSPACE(s(n)\subseteq SPACE(s^{2}(n))$

في حين أنَّ ((NSPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج غير قطعية التي تستغل (s(n مساحة اضافية على الأكثر، ((SPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج قطعية التي تستغل (s(n مساحة اضافية على الأكثر.

البرهان

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

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

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

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

الخوارزمية

من الملاحظات السابقة يظهر انه ليتحقق (Reach(u,v,i=«نعم» يكفي ان نجد z الذي يحقق (1-Reach(u,z,i=«نعم» و (1-Reach(z,v,i=«نعم», لذا كل ما علينا فعله هو إيجاد z يحقق المطلوب، لذا فاننا سوف نبحث عنه عودياً (recursively):

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

نلحظ انه يمكن استخدام المساحة التي قد استخدمت سابقا، لذا فان المساحة الاضافية يمكن التعبير عنها بالشكل التالي:

$s_{m,i}=s_{m,i-1}+O(log(m))$ لذا من الملاحظة الأولى: لنحل مسألة الوصول ((i=O(log(m أي: $s_{m,log(m)}=s_{m,log(m)-1}+O(log(m))$ وحل هذه العلاقة العودية هو $s_{m,log(m)}=log^{2}(m)=O(s^{2}(n))$ وهذا هو المطلوب.

استنتاجات

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

انظر أيضا

مصادر

Arora، Sanjeev؛ Barak، Boaz (2009)، Computational complexity. A modern approach، Cambridge University Press، ISBN:978-0-521-42426-4، Zbl:1193.68112
Papadimitriou، Christos (1993)، "Section 7.3: The Reachability Method"، Computational Complexity (ط. 1st)، Addison Wesley، ص. 149–150، ISBN:0-201-53082-1
Savitch، Walter J. (1970)، "Relationships between nondeterministic and deterministic tape complexities"، Journal of Computer and System Sciences، ج. 4، ص. 177–192، DOI:10.1016/S0022-0000(70)80006-X
Sipser، Michael (1997)، "Section 8.1: Savitch's Theorem"، Introduction to the Theory of Computation، PWS Publishing، ص. 279–281، ISBN:0-534-94728-X