الفراغ اللوغاريتيمي اللابتري
في نظرية التعقيد التحسيبي، الفراغ اللوغاريتيمي اللابتري' NL (الإنكليزية: Nondeterministic Logarithmic-space)، هوأحد أصناف التعقيد التي تضم مسائل القرار التي يمكن حلها باستخدام آلة تورنگ اللابترية في حجم ذاكرة لوغاريتيمي.
يعتبر صنف NL تعميماً لصنف L، مجموعة مسائل فراغ لوغاريتمية على آلة تورنگ البترية. وبما أنه تعتبر جميع آلة تورنگ البترية آلة لابترية أيضاً، فإن صنف Lقد يكون محتوىً في صنف NL.
يمكن تعريف صنف NL أيضاً بشكل صوري بالاعتماد على الفراغ اللابتري (أواختصاراً NSPACE) أحد الموارد التحسيبية، حيث : (NL = NSPACE(log n
مراجع
- نطقب:CZoo
- Papadimitriou, C. (1994). "Chapter 16: Logarithmic Space". Computational Complexity. Addison-Wesley. ISBN .
- Michael Sipser (1997). "Sections 8.4-8.6: The Classes L and NL, NL-completeness, NL equals coNL". Introduction to the Theory of Computation. PWS Publishing. pp. 294–302. ISBN .
- Introduction to Complexity Theory: Lecture 7. Oded Goldreich. Proposition 6.1. Our C is what Goldreich calls badRSPACE(log n).
