مبرهنة سافيتش: الفرق بين النسختين
| [نسخة منشورة] | [نسخة منشورة] |
تم حذف المحتوى تمت إضافة المحتوى
ط تدقيق إملائي يستهدف همزات القطع (المزيد) |
ط تهذيب، وتنسيق ويكي.. باستخدام أوب |
||
سطر 1:
في نظرية التعقيد الحسابي '''مبرهنة سافيتش''' هي نتيجة اساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي . ونص المبرهنة هو :
<center>
<math> \forall s(n)>log(n) \mbox{ } , \mbox{ } NSPACE(s(n) \subseteq SPACE(s^2(n))</math>
</center>
في حين أنَّ ((NSPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة الة تيورنج غير قطعية التي تستغل (s(n مساحة اضافية على الاكثر , ((SPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة الة تيورنج قطعية التي تستغل (s(n مساحة اضافية على الاكثر .
==البرهان==
فلتكن <math> L\in NSPACE(s(n))</math> لغة التي يمكن تقريرها بواسطة الة تيورنج غير قطعية , M , التي تستغل (s(n مساحة اضافية . لكل <math> x\in \{0,1\}^* </math> [[آلة تورنج#صورة الة تيورنج|مخطط الصُوَر]] , G=G<sub>M,x</sub> , يوجد فيه على الاكثر <math> m=2^{s(n)} </math> رؤوس . لاحظ انَّ <math> x\in L </math> فقط اذا يوجد من الصورة الاولية , نرمز لها s , مسار موجه إلى الصورة النهائية , نرمز لها t , هذه المسألة تُعرف أيضا بمسألة الوصول وهي مسألة تقرير : معطى مخطط G , وكذلك رأسين s و-t ,قرر اذا ما يوجد مسار موجه بين s و- t . يمكن حل هذه المسألة بسهولة بواسطة DFS او BFS ولكن المساحة الاضافية المستخدمة خطية (اي <math>2^{O(s)}</math>) وهذا لا يفيد للمبرهنة .
نعرف (Reach(u,v,i على انه "نعم" اذا يوجد مسار بين u و- v طوله على الاكثر 2<sup>i</sup> و"لا" خلاف هذا . لاحظ انه :
# ((Reach(s,t,log(n = "نعم" فقط اذا يوجد مسار بين s و- t . (اي انه يمكننا حل مسألة الوصول)
# (Reach(u,v,i="نعم" <math> \iff</math> يوجد رأس z بحيث يمكن الوصول من u إلى z وطول المسار بينهما على الاكثر <math>2^{i-1}</math> , ويمكن الوصول من z إلى v حيث ان طول المسار بينهما على الاكثر <math>2^{i-1}</math> .
بواسطة هذه الملاحظات امكن ان نحصل على خوارزمية عودية والتي مساحتها الاضافية التي تستخدمها على الاكثر هي <math> O(s^2(n))</math> .
===الخوارزمية===
سطر 30:
</source>
نلحظ انه يمكن استخدام المساحة التي قد استخدمت سابقا , لذا فان المساحة الاضافية يمكن التعبير عنها بالشكل التالي :
<math> s_{m,i}=s_{m,i-1}+O(log(m))</math> لذا من الملاحظة الاولى : لنحل مسألة الوصول ((i=O(log(m اي : <math> s_{m,log(m)}=s_{m,log(m)-1}+O(log(m))</math> وحل هذه العلاقة العودية هو <math> s_{m,log(m)}=log^2(m)=O(s^2(n))</math> وهذا هو المطلوب .
==استنتاجات==
* PSPACE=NPSPACE , وهذا لان تربيع كثير الحدود هو أيضا كثير حدود .
* NL⊆L<sup>2</sup> حيث أنَّ ((L<sup>2</sup>=SPACE(log<sup>2</sup>(n , وهذا ينبع من المبرهنة مباشرة , وكذلك لان مسألة الوصول هي مسألة كاملة في الصنف NL .
==انظر أيضا==
سطر 72:
| year = 1997}}
</div>
[[تصنيف:مبرهنات التعقيد الحسابي]]
| |||