يرجى إضافة وصلات داخلية للمقالات المتعلّقة بموضوع المقالة.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث

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

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

البرهان[عدل]

فلتكن لغة التي يمكن تقريرها بواسطة آلة تيورنج غير قطعية , M , التي تستغل (s(n مساحة اضافية . لكل مخطط الصُوَر , G=GM,x , يوجد فيه على الأكثر رؤوس . لاحظ انَّ فقط اذا يوجد من الصورة الاولية , نرمز لها s , مسار موجه إلى الصورة النهائية , نرمز لها t , هذه المسألة تُعرف أيضا بمسألة الوصول وهي مسألة تقرير : معطى مخطط G , وكذلك رأسين s و-t ,قرر اذا ما يوجد مسار موجه بين s و- t . يمكن حل هذه المسألة بسهولة بواسطة DFS او BFS ولكن المساحة الاضافية المستخدمة خطية (اي ) وهذا لا يفيد للمبرهنة .

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

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

بواسطة هذه الملاحظات امكن ان نحصل على خوارزمية عودية والتي مساحتها الاضافية التي تستخدمها على الأكثر هي .

الخوارزمية[عدل]

من الملاحظات السابقة يظهر انه ليتحقق (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

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

لذا من الملاحظة الاولى : لنحل مسألة الوصول ((i=O(log(m اي : وحل هذه العلاقة العودية هو وهذا هو المطلوب .

استنتاجات[عدل]

  • PSPACE=NPSPACE , وهذا لان تربيع كثير الحدود هو أيضا كثير حدود .
  • NL⊆L2 حيث أنَّ ((L2=SPACE(log2(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 (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، ISBN 0-534-94728-X