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

☰ جدول المحتويات

نبذة تمهيدية
البرهان
- الخوارزمية
استنتاجات
مقالات ذات صلة
مصادر

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

$\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, , Zbl = complete&q = an:1193.68112 1193.68112
Papadimitriou, Christos (1993), "Section 7.3: The Reachability Method", Computational Complexity (الطبعة 1st), Addison Wesley, صفحات 149–150,
Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences, 4 (2): 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,

موسوعات ذات صلة :

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