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

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

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

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوقة. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018)

هذه المقالة يتيمة إذ لا تصل إليها مقالة أخرى. ساعد بإضافة وصلة إليها في مقالة متعلقة بها. (أكتوبر 2015)

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (أغسطس 2015)

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

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

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