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

في نظرية التعقيد الحسابي ان إل (غير قطعية لوغارتمية المساحة) (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 تنتمي إلى القسم القابل للحل قطعيا في مربع لوغاريتم من المساحة

$\mathsf{N}\mathsf{L}\mathsf{\subseteq }\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}({\log }^{2}n)$