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

أُضيف 22 بايت ، ‏ قبل سنة واحدة
ط
بوت: صيانة، obsolete-tag
(وصل 1 كتب للتحقق منها) #IABot (v2.1alpha3)
ط (بوت: صيانة، obsolete-tag)
{{وصلات قليلة|تاريخ=نوفمبر 2017}}
في نظرية التعقيد الحسابي '''مبرهنة سافيتش''' هي نتيجة اساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي . ونص المبرهنة هو :
<div style="text-align: center;">
<math> \forall s(n)>log(n) \mbox{ } , \mbox{ } NSPACE(s(n) \subseteq SPACE(s^2(n))</math>
</centerdiv>
 
في حين أنَّ ((NSPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج غير قطعية التي تستغل (s(n مساحة اضافية على الأكثر , ((SPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج قطعية التي تستغل (s(n مساحة اضافية على الأكثر .
6٬868٬803

تعديل