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

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

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

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

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

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