تبرهن مبرهنة سافيتش أن إدخال لامحدودية الاختيار في نظرية التعقيد الحسابي يترك أثرًا محدودًا على تعقيد المساحة، إذ تنص المبرهنة على أن أي خوارزمية غير حتمية تستخدم كمية من الذاكرة يحدِّدها دالة بالنسبة لحجم المدخلات يمكن محاكاتها بخوارزمية حتمية تستخدم ذاكرة لا تزيد سوى بمقدار مربع تلك الدالة. يستند برهان المبرهنة إلى فكرة استقصاء رسم الحالة الناتج عن الحوسبة غير الحتمية بطريقة تقسيمية، حيث تُقسَم مهمة التحقق من وجود مسار مقبول بين حالتين إلى مهام أصغر وتُجرى محاكاة متكررة دون الحاجة إلى حفظ جميع المسارات في الذاكرة، ما يؤدي إلى زيادة في استهلاك المساحة بمقدار تربيعي تقريبًا بدلًا من زيادة هائلة، ومن ثم تُقيِّد المبرهنة الفجوة بين القدرة الحاسوبية غير الحتمية والحتمية عند قياسها بالمساحة بشكل صارم على أساس تربيعي.