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

Nuvola apps edu mathematics-ar.svg
هذه بذرة مقالة عن الرياضيات بحاجة للتوسيع. شارك في تحريرها.