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

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

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

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

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

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

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

وصلات داخلية

روابط خارجية

مصادر

بوابة رياضيات

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.