مبرهنة اميرمان-زليبتسيني

مبرهنة اميرمان-زليبتسيني نتيجتها الاساسية متعلقة بمورد المكان لاّلات تيورنج، ولها صيغتان معتمدتان:

1. $\text{NPSPACE(s(n))=Co-NPSPACE(s(n))}$ عندما: $\text{s(n)}\ge \text{log(n)}$
2. $\text{NL=Co-NL}$

نلحظ ان الصيغتين متكافئتين وذلك لاننا نستطيع ان نحصل على "2" من "1" وذلك عندما: $\text{s(n)=log(n)}$ ونحصل على "1" من "2" بواسطة البرهنة بالحشو.

وبشكل اخر يمكن القول بأن المبرهنة تقول: ان كل ما استطعت حله بآلة غير حتمية بكمية مكان اضافي معينة حينها يمكن حل المسألة المكملة بنفس الكمية تقريبا بشكل غير حتمي أيضا.

وقد برهن هذه المبرهنة اثنين بشكل مستقل عام 1987 وهما نييل اميرمان وروبيرت زليبتسيني وعام 1995 اشتركا في جائزة جودل في مجال علوم الحاسوب، وقد كانت المبرهنة حدسية لمدة 20 عامًا حتى تم برهنتها. صيغت المسألة لأول مرة عام 1967 في مقال مميز لكورودا سيجو.