NL (تعقيد حسابي)
تعريفًا بالموضوع، في نظرية التعقيد الحسابي ان إل (غير قطعية لوغارتمية المساحة) (nondetereministic logarithmic-space) NL هي قسم من اللغات الصورية تضم مسائل التقرير التي يمكن حلها باستخدام كمية لوغارتمية من الذاكرة بواسطة آلة تورينغ غير قطعية. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
وفي هذا السياق، NL هي تعميم لL وهي قسم المسائل اللوغارتمية المكان القطعية، وحيث إن كل آلة تورينغ قطعية هي كذلك آلة تورينغ غير قطعية، فإن L تنتمي إلى NL.
العلاقة مع أقسام التعقيد الأخرى
علاوةً على ذلك، باستخدام نظرية سافيتش Savitch's theorem ، والتي تنص على أن أي خوارزمية غير قطعية يمكن محاكاتها باستخدام آلة قطعية في مربع المكان الذي تستعمله الخوارزمية الأصلية، يمكننا استنتاج أن NL تنتمي إلى القسم القابل للحل قطعيا في مربع لوغاريتم من المساحة
إضافةً إلى ذلك، من المعلوم أن NL تنتمي إلى P، وذلك لوجود خوارزميات معروفة كثيرة الحدود في الزمن لمسائل NL الكاملة. لكن تظل L = NL و NL = P مسألتين مفتوحتين. من المعلوم كذلك أن NL = co-NL حيث co-NL هي مجموعة اللغات اللتي متمماتها في NL، وهذه هي نظرية إمرمان-سلبتشني (Immerman-Szelepcsényi) التي أثبتها كل واحد منهما مستقلا عام 1987م.
مسائل NL الكاملة
من جهة ثانية، من مسائل NL الكاملة المعروفة، اتصال نقطتين في رسم بياني موجه، و 2SAT.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟