افتح القائمة الرئيسية
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018)

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

في حين أنَّ ((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