مبرهنة سافيتش: الفرق بين النسختين

لا تغيير في الحجم ، ‏ قبل 7 سنوات
ط
تدقيق إملائي يستهدف همزات القطع (المزيد)
ط (تدقيق إملائي يستهدف حروف الجر (المزيد))
ط (تدقيق إملائي يستهدف همزات القطع (المزيد))
 
==البرهان==
فلتكن <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> و"لا" خلاف هذا . لاحظ انه :
 
==استنتاجات==
* PSPACE=NPSPACE , وهذا لان تربيع كثير الحدود هو ايضاأيضا كثير حدود .
* NL&sube;L<sup>2</sup> حيث أنَّ ((L<sup>2</sup>=SPACE(log<sup>2</sup>(n , وهذا ينبع من المبرهنة مباشرة , وكذلك لان مسألة الوصول هي مسألة كاملة في الصنف NL .
 
==انظر ايضاأيضا==
* [[مبرهنة اميرمان-زليبتسيني]]
* [[PSPACE]]
298٬388

تعديل