الدليل الشامل لـ مبرهنة سافيتش

في نظرية التعقيد الحسابي مبرهنة سافيتش هي نتيجة أساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي. ونص المبرهنة هو:



في حين أنَّ ((NSPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج غير قطعية التي تستغل (s(n مساحة اضافية على الأكثر، ((SPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج قطعية التي تستغل (s(n مساحة اضافية على الأكثر.