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

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

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

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

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