مرجع
آخر الزيارات

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

404 كلمة•0 مشاهدة•🗒️ منذ يوم
باختصار: في نظرية التعقيد الحسابي مبرهنة سافيتش هي نتيجة أساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي. تجد هنا «البرهان»، «return false» و«return s == t» ضمن 5 أقسام.
المحتويات
  1. البرهان
  2. return false
  3. return s == t
  4. استنتاجات
  5. الخوارزمية

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

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

البرهان

ومن ناحية أخرى، ((Reach(s,t,log(n = «نعم» فقط إذا يوجد مسار بين s و- t . (أي انه يمكننا حل مسألة الوصول)

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

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

وعلى صعيد آخر، (Reach(u,v,i=«نعم» يوجد رأس z بحيث يمكن الوصول من u إلى z وطول المسار بينهما على الأكثر , ويمكن الوصول من z إلى v حيث ان طول المسار بينهما على الأكثر .

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

return false

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

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

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

استنتاجات

من جهة ثانية، NL⊆L2 حيث أنَّ ((L2=SPACE(log2(n , وهذا ينبع من المبرهنة مباشرة، وكذلك لان مسألة الوصول هي مسألة كاملة في الصنف NL .

وفي هذا الصدد، PSPACE=NPSPACE , وهذا لان تربيع كثير الحدود هو كذلك كثير حدود.

  • انظر كذلك
  • مبرهنة اميرمان-زليبتسيني
  • بيسبايس

الخوارزمية

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.