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

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

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

  1. عندما :

نلحظ ان الصيغتين متكافئتين وذلك لاننا نستطيع ان نحصل على "2" من "1" وذلك عندما : ونحصل على "1" من "2" بواسطة البرهنة بالحشو .

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

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

وصلات داخليةعدل

روابط خارجيةعدل

مصادرعدل

 
هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. شارك في تحريرها.