مبرهنة سافيتش: الفرق بين النسختين
[نسخة منشورة] | [نسخة منشورة] |
Mr.Ibrahembot (نقاش | مساهمات) ط بوت: صيانة، obsolete-tag |
ط Bot: Replace deprecated <source> tag and "enclose" parameter، تغييرات تجميلية |
||
سطر 1: | سطر 1: | ||
{{مصدر|تاريخ=ديسمبر 2018}} |
{{مصدر|تاريخ=ديسمبر 2018}} |
||
{{وصلات قليلة|تاريخ=نوفمبر 2017}} |
{{وصلات قليلة|تاريخ=نوفمبر 2017}} |
||
في نظرية التعقيد الحسابي '''مبرهنة سافيتش''' هي نتيجة اساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي . ونص المبرهنة هو : |
في نظرية التعقيد الحسابي '''مبرهنة سافيتش''' هي نتيجة اساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي . ونص المبرهنة هو : |
||
<div style="text-align: center;"> |
<div style="text-align: center;"> |
||
<math> \forall s(n)>log(n) \mbox{ } , \mbox{ } NSPACE(s(n) \subseteq SPACE(s^2(n))</math> |
<math> \forall s(n)>log(n) \mbox{ } , \mbox{ } NSPACE(s(n) \subseteq SPACE(s^2(n))</math> |
||
سطر 8: | سطر 8: | ||
في حين أنَّ ((NSPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج غير قطعية التي تستغل (s(n مساحة اضافية على الأكثر , ((SPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج قطعية التي تستغل (s(n مساحة اضافية على الأكثر . |
في حين أنَّ ((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>) وهذا لا يفيد للمبرهنة . |
فلتكن <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(u,v,i على انه "نعم" اذا يوجد مسار بين u و- v طوله على الأكثر 2<sup>i</sup> و"لا" خلاف هذا . لاحظ انه : |
||
# ((Reach(s,t,log(n = "نعم" فقط اذا يوجد مسار بين s و- t . (اي انه يمكننا حل مسألة الوصول) |
# ((Reach(s,t,log(n = "نعم" فقط اذا يوجد مسار بين s و- t . (اي انه يمكننا حل مسألة الوصول) |
||
# (Reach(u,v,i="نعم" <math> \iff</math> يوجد رأس z بحيث يمكن الوصول من u إلى z وطول المسار بينهما على الأكثر <math>2^{i-1}</math> , ويمكن الوصول من z إلى v حيث ان طول المسار بينهما على الأكثر |
# (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> . |
بواسطة هذه الملاحظات امكن ان نحصل على خوارزمية عودية والتي مساحتها الاضافية التي تستخدمها على الأكثر هي <math> O(s^2(n))</math> . |
||
===الخوارزمية=== |
=== الخوارزمية === |
||
من الملاحظات السابقة يظهر انه ليتحقق (Reach(u,v,i="نعم" يكفي ان نجد z الذي يحقق (1-Reach(u,z,i="نعم" و (1-Reach(z,v,i="نعم" , لذا كل ما علينا فعله هو ايجاد z يحقق المطلوب , لذا فاننا سوف نبحث عنه عودياً (recursively) : |
من الملاحظات السابقة يظهر انه ليتحقق (Reach(u,v,i="نعم" يكفي ان نجد z الذي يحقق (1-Reach(u,z,i="نعم" و (1-Reach(z,v,i="نعم" , لذا كل ما علينا فعله هو ايجاد z يحقق المطلوب , لذا فاننا سوف نبحث عنه عودياً (recursively) : |
||
< |
<syntaxhighlight lang="python"> |
||
def k_edge_path(s, t, k): |
def k_edge_path(s, t, k): |
||
if k == 0: |
if k == 0: |
||
سطر 30: | سطر 30: | ||
return true |
return true |
||
return false |
return false |
||
</syntaxhighlight> |
|||
</source> |
|||
نلحظ انه يمكن استخدام المساحة التي قد استخدمت سابقا , لذا فان المساحة الاضافية يمكن التعبير عنها بالشكل التالي : |
نلحظ انه يمكن استخدام المساحة التي قد استخدمت سابقا , لذا فان المساحة الاضافية يمكن التعبير عنها بالشكل التالي : |
||
سطر 36: | سطر 36: | ||
<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> وهذا هو المطلوب . |
<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 , وهذا لان تربيع كثير الحدود هو أيضا كثير حدود . |
* PSPACE=NPSPACE , وهذا لان تربيع كثير الحدود هو أيضا كثير حدود . |
||
* |
* NL⊆L<sup>2</sup> حيث أنَّ ((L<sup>2</sup>=SPACE(log<sup>2</sup>(n , وهذا ينبع من المبرهنة مباشرة , وكذلك لان مسألة الوصول هي مسألة كاملة في الصنف NL . |
||
==انظر أيضا== |
== انظر أيضا == |
||
* [[مبرهنة اميرمان-زليبتسيني]] |
* [[مبرهنة اميرمان-زليبتسيني]] |
||
* [[بيسبايس]] |
* [[بيسبايس]] |
||
==مصادر== |
== مصادر == |
||
<div dir="LTR"> |
<div dir="LTR"> |
||
* {{citation | zbl=1193.68112 | الأخير1=Arora | الأول1=Sanjeev | الأخير2=Barak | الأول2=Boaz | العنوان=Computational complexity. A modern approach | الناشر=Cambridge University Press | السنة=2009 | isbn=978-0-521-42426-4 }} |
* {{citation | zbl=1193.68112 | الأخير1=Arora | الأول1=Sanjeev | الأخير2=Barak | الأول2=Boaz | العنوان=Computational complexity. A modern approach | الناشر=Cambridge University Press | السنة=2009 | isbn=978-0-521-42426-4 }} |
||
*{{citation |
* {{citation |
||
| الأخير = Papadimitriou | الأول = Christos |
| الأخير = Papadimitriou | الأول = Christos |
||
| contribution = Section 7.3: The Reachability Method |
| contribution = Section 7.3: The Reachability Method |
||
سطر 56: | سطر 56: | ||
| العنوان = Computational Complexity |
| العنوان = Computational Complexity |
||
| السنة = 1993}} |
| السنة = 1993}} |
||
*{{citation |
* {{citation |
||
| الأخير = Savitch | الأول = Walter J. |
| الأخير = Savitch | الأول = Walter J. |
||
| doi = 10.1016/S0022-0000(70)80006-X |
| doi = 10.1016/S0022-0000(70)80006-X |
||
سطر 65: | سطر 65: | ||
| volume = 4 |
| volume = 4 |
||
| السنة = 1970}} |
| السنة = 1970}} |
||
*{{citation |
* {{citation |
||
| الأخير = Sipser |
| الأخير = Sipser |
||
| الأول = Michael |
| الأول = Michael |
نسخة 20:57، 17 أبريل 2020
يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. (ديسمبر 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 و"لا" خلاف هذا . لاحظ انه :
- ((Reach(s,t,log(n = "نعم" فقط اذا يوجد مسار بين s و- t . (اي انه يمكننا حل مسألة الوصول)
- (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