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 تنتمي إلى القسم القابل للحل قطعيا في مربع لوغاريتم من المساحة
- ع
- ن
- ت
- DLOGTIME
- AC0
- ACC0
- TC0
- L
- SL
- RL
- NL
- NC
- SC
- CC
- P
- P-complete
- ZPP
- RP
- BPP
- BQP
- يو بي
- كثير حدود غير قطعي
- أي إم
- PH
- بي الزوجي
- بي بي
- P#
- مسائل P# كاملة
- IP
- بيسبايس (مسائل PSPACE كاملة)
- EXPTIME
- NEXPTIME
- EXPSPACE
- ELEMENTARY
- PR
- R
- RE
- ALL
- Polynomial hierarchy
- Exponential hierarchy
- Grzegorczyk hierarchy
- Arithmetic hierarchy
- Boolean hierarchy
- DTIME
- NTIME
- DSPACE
- NSPACE
- براهين قابلة للفحص بشكل احتمالي
- نظام براهين تفاعلي
- بوابة رياضيات
- بوابة علم الحاسوب
هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها. |