NL (التعقيد)

NL هي فئة التعقيد لمشاكل القرار التي يمكن حلها بواسطة آلة تورينج غير الحتمية (NTM) باستخدام كمية لوغاريتمية من مساحة الذاكرة.

بتفصيل أكثر، لغة${\displaystyle L}$هو NL إذا وُجد NTM${\displaystyle M}$بحيث

• ${\displaystyle M}$يعمل على مساحة السجل.
• ${\displaystyle M}$يتوقف دائماً.

• لو${\displaystyle x\in L}$إذن، يوجد على الأقل أثر حسابي واحد لـ${\displaystyle M(x)}$مما يؤدي إلى توقف الجهاز في حالة قبول.
• لو${\displaystyle x\not \in L}$ثم جميع الآثار الحسابية لـ${\displaystyle M(x)}$يؤدي ذلك إلى توقف الجهاز في حالة عدم قبول.

لنفترض أن C هي فئة تعقيد مسائل القرار القابلة للحل في فضاء لوغاريتمي باستخدام آلات تورينغ احتمالية لا تقبل أبدًا بشكل خاطئ، ولكن يُسمح لها بالرفض بشكل خاطئ في أقل من ثلث الوقت؛ وهذا ما يُسمى بالخطأ أحادي الجانب . الثابت 1/3 اختياري؛ أي قيمة لـ x حيث 0 ≤ x < 1/2 تكفي.

اتضح أن C = NL . لاحظ أن C ، على عكس نظيرتها الحتمية L ، لا تقتصر على زمن متعدد الحدود، لأنه على الرغم من امتلاكها عددًا متعدد الحدود من التكوينات، إلا أنها تستطيع استخدام العشوائية للخروج من حلقة لا نهائية. إذا قمنا بتقييدها بزمن متعدد الحدود، فسنحصل على الفئة RL ، التي تندرج ضمن NL ولكن ليس من المعروف أو يُعتقد أنها تساويها .

توجد خوارزمية بسيطة تثبت أن C = NL . من الواضح أن C مُحتواة في NL ، لأن:

• إذا لم تكن السلسلة موجودة في اللغة، فسيتم رفضها على طول جميع مسارات الحساب.
• إذا كانت السلسلة في اللغة، فإن خوارزمية NL تقبل على طول مسار حساب واحد على الأقل، وخوارزمية C تقبل على طول ثلثي مسارات حسابها على الأقل.

لإثبات أن NL مُحتوى في C ، نأخذ ببساطة خوارزمية NL ونختار مسار حساب عشوائي بطول n ، وننفذه 2 ^{^n} مرة. ولأن أي مسار حساب لا يتجاوز طوله n ، ولأن هناك 2 ^{^n} مسار حساب إجمالاً، فإن لدينا فرصة جيدة للوصول إلى المسار المقبول (محدود من الأسفل بثابت).

المشكلة الوحيدة هي عدم وجود مساحة كافية في فضاء اللوغاريتمات لعداد ثنائي يصل إلى 2^ ⁿ . ولتجاوز هذه المشكلة، نستبدله بعداد عشوائي ، يقوم ببساطة برمي n قطعة نقدية ويتوقف ويرفض إذا ظهرت جميعها على صورة. بما أن احتمال هذا الحدث هو 2^ n ^{- 2 ^n} ، نتوقع أن يقطع 2^ ⁿ خطوة في المتوسط ​​قبل التوقف. كل ما يحتاجه هو الاحتفاظ بمجموع تراكمي لعدد مرات ظهور الصورة في صف واحد، وهو ما يمكن حسابه في فضاء اللوغاريتمات.

بفضل نظرية إيمرمان-سيليبسيني ، التي تنص على أن مجموعة NL مغلقة تحت المكملات، يمكن استبدال الخطأ أحادي الجانب في هذه الحسابات الاحتمالية بخطأ صفري الجانب. أي أن هذه المسائل يمكن حلها بواسطة آلات تورينغ الاحتمالية التي تستخدم مساحة لوغاريتمية ولا ترتكب أي أخطاء. يُطلق على فئة التعقيد المقابلة التي تتطلب أيضًا من الآلة استخدام وقت متعدد الحدود فقط اسم ZPLP .

وهكذا، عندما ننظر فقط إلى الفضاء، يبدو أن العشوائية وعدم الحتمية متساويتان في القوة.

يمكن وصف NL بشكل مكافئ بالشهادات ، على غرار فئات مثل NP . لنفترض أن المدقق هو آلة تورينغ حتمية محدودة في الفضاء اللوغاريتمي، والتي تحتوي على شريط إدخال إضافي للقراءة مرة واحدة فقط (أي أن المدقق لا يمكنه تحريك رأس القراءة إلا للأمام، وليس للخلف).

لغة${\displaystyle L}$تكون في اللغة الهولندية إذا وفقط إذا ^{[ 1 ] : التعريف 4.19}

• توجد دالة متعددة الحدود${\displaystyle p}$.
• يوجد مدقق${\displaystyle TM}$.
• لأي${\displaystyle x}$،${\displaystyle x\in L}$إذا كانت هناك شهادة${\displaystyle u}$مع الطول${\displaystyle |u|\leq p(|x|)}$بحيث${\displaystyle TM(x,u)=1}$.

بمعنى آخر، إذا كانت الجملة تنتمي إلى اللغة، فإنه يوجد برهانٌ ذو طول متعدد الحدود يثبت ذلك. ولا يُشير هذا إلى حالة عدم انتمائها إلى اللغة ، مع أنه من الواضح، وفقًا لنظرية إيمرمان-سيليبسيني، وجود مُدقِّقٍ ما يُمكنه التحقق من كلا الحالتين.${\displaystyle x\in L}$و${\displaystyle x\not \in L}$.

لاحظ أن شرط القراءة لمرة واحدة ضروري. إذا كان بإمكان المُدقِّق القراءة للأمام وللخلف، فإن هذا يُوسِّع الفئة لتشمل فئة NP . ^{[ 1 ] : التمرين 4.7}

أثبت كل من جيم ساي وأبوزير ياكارييلماز أن آلة تورينج الحتمية ذات الفضاء اللوغاريتمي المذكورة أعلاه يمكن استبدالها بآلة تورينج احتمالية ذات فضاء ثابت ذات خطأ محدود، والتي يُسمح لها باستخدام عدد ثابت فقط من البتات العشوائية. ^{[ 2 ]}

في نظرية التعقيد الوصفي ، يتم تعريف NL على أنها تلك اللغات التي يمكن التعبير عنها في منطق الرتبة الأولى مع إضافة عامل إغلاق متعدٍ .