NL (تعقيد حسابي)

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

في نظرية التعقيد الحسابي ان إل (غير قطعية لوغارتمية المساحة) (nondetereministic logarithmic-space) NL هي قسم من اللغات الصورية تضم مسائل التقرير التي يمكن حلها باستخدام كمية لوغارتمية من الذاكرة بواسطة آلة تورينغ غير قطعية.

NL هي تعميم لL وهي قسم المسائل اللوغارتمية المكان القطعية، وحيث إن كل آلة تورينغ قطعية هي أيضا آلة تورينغ غير قطعية، فإن L تنتمي إلى NL.

مسائل NL الكاملةعدل

من مسائل NL الكاملة المعروفة، اتصال نقطتين في رسم بياني موجه، و 2SAT.


العلاقة مع أقسام التعقيد الأخرىعدل

من المعلوم أن NL تنتمي إلى P، وذلك لوجود خوارزميات معروفة كثيرة الحدود في الزمن لمسائل NL الكاملة. لكن تظل L = NL و NL = P مسألتين مفتوحتين. من المعلوم أيضا أن NL = co-NL حيث co-NL هي مجموعة اللغات اللتي متمماتها في NL، وهذه هي نظرية إمرمان-سلبتشني (Immerman-Szelepcsényi) التي أثبتها كل واحد منهما مستقلا عام 1987م.

باستخدام نظرية سافيتش Savitch's theorem ، والتي تنص على أن أي خوارزمية غير قطعية يمكن محاكاتها باستخدام آلة قطعية في مربع المكان الذي تستخدمه الخوارزمية الأصلية، يمكننا استنتاج أن NL تنتمي إلى القسم القابل للحل قطعيا في مربع لوغاريتم من المساحة

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