الفراغ اللوغاريتيمي اللاقطعي

في نظرية التعقيد التحسيبي، الفراغ اللوغاريتيمي اللاقطعي' 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 0-201-53082-1.
• 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 0-534-94728-X.
• Introduction to Complexity Theory: Lecture 7. Oded Goldreich. Proposition 6.1. Our C is what Goldreich calls badRSPACE(log n).