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

أُضيف 208 بايت ، ‏ قبل سنة واحدة
ط
بوت:إضافة مصدر (1.3)، إزالة وسم مصدر
ط (بوت:إصلاح تحويلات القوالب)
ط (بوت:إضافة مصدر (1.3)، إزالة وسم مصدر)
{{مصدر|تاريخ=ديسمبر 2018}}
{{وصلات قليلة|تاريخ=نوفمبر 2017}}
في نظرية التعقيد الحسابي '''مبرهنة سافيتش''' هي نتيجة اساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي .<ref>{{استشهاد ويب| مسار = https://academic.microsoft.com/v2/detail/47796627 | عنوان = معلومات عن مبرهنة سافيتش على موقع academic.microsoft.com | ناشر = academic.microsoft.com}}</ref> ونص المبرهنة هو :
<div style="text-align: center;">
<math> \forall s(n)>log(n) \mbox{ } , \mbox{ } NSPACE(s(n) \subseteq SPACE(s^2(n))</math>
 
== مصادر ==
{{مراجع}}
 
<div dir="LTR">
* {{استشهاد | 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 }}