مبرهنة سافيتش: الفرق بين النسختين
| [نسخة منشورة] | [نسخة منشورة] |
تم حذف المحتوى تمت إضافة المحتوى
ط Bot: Replace deprecated <source> tag and "enclose" parameter، تغييرات تجميلية |
ط بوت:تدقيق إملائي V1.6 |
||
سطر 9:
== البرهان ==
فلتكن <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> فقط
نعرف (Reach(u,v,i على انه "نعم"
# ((Reach(s,t,log(n = "نعم" فقط
# (Reach(u,v,i="نعم" <math> \iff</math> يوجد رأس z بحيث يمكن الوصول من u إلى z وطول المسار بينهما على الأكثر <math>2^{i-1}</math> , ويمكن الوصول من z إلى v حيث ان طول المسار بينهما على الأكثر <math>2^{i-1}</math> .
سطر 18:
=== الخوارزمية ===
من الملاحظات السابقة يظهر انه ليتحقق (Reach(u,v,i="نعم" يكفي ان نجد z الذي يحقق (1-Reach(u,z,i="نعم" و (1-Reach(z,v,i="نعم" , لذا كل ما علينا فعله هو ايجاد z يحقق
<syntaxhighlight lang="python">
def k_edge_path(s, t, k):
سطر 32:
</syntaxhighlight>
نلحظ انه يمكن استخدام المساحة التي قد استخدمت
<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> وهذا هو المطلوب .
سطر 38:
== استنتاجات ==
* PSPACE=NPSPACE , وهذا لان تربيع كثير الحدود هو أيضا كثير حدود .
* NL⊆L<sup>2</sup> حيث أنَّ ((L<sup>2</sup>=SPACE(log<sup>2</sup>(n , وهذا ينبع من المبرهنة
== انظر أيضا ==
| |||