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

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

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

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

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

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

وصلات داخلية

روابط خارجية

مصادر

موسوعات ذات صلة :

• موسوعة رياضيات