L (تعقيد)

في نظرية التعقيد التحسيبي، L (وأيضاً يشار إليه بالاختصار LSPACE) هو أحد أصناف التعقيد الذي يضم مجموعة مسائل القرار التي يمكن حلها باستخدام آلة تورنگ القطعية في حجم ذاكرة لوغاريتيمي.


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

الهامش

  • Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1.CS1 maint: extra text (link) Chapter 16: Logarithmic space, pp.395-408.
  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 8.4: The Classes L and NL, pp.294-296.
  • Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. Section 7.5: Logarithmic Space, pp.177-181.