L (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, L (còn gọi là LSPACE) là lớp độ phức tạp bao gồm các bài toán quyết định có thể giải bằng máy Turing đơn định trong không gian/bộ nhớ lôgarit. Bộ nhớ lôgarit là đủ để lưu một hằng số các con trỏ vào dữ liệu vào, một số lôgarit các biến lôgic, và một số lôgarit các ô nhớ để dùng vào việc khác.

L là tập hợp con của NL, lớp các bài toán giải được trong bộ nhớ lôgarit trên máy Turing không đơn định. Theo chứng minh của định lý Savitch, NL là tập hợp con của P, lớp các bài toán giải được trong thời gian đa thức. Vì vậy L ⊆ NL ⊆ P. Cũng có thể chứng minh trực tiếp L là tập hợp con của P như sau: một máy Turing dùng bộ nhớ O(log n) không thể chạy trong thời gian lâu hơn 2^O(log n) = n^O(1) mà không lặp vô hạn vì đây là số lượng tối đa các trạng thái của máy.

Mọi bài toán không tầm thường trong L là đầy đủ theo phép quy về trong không gian lôgarit nên cần dùng phép quy về yếu hơn để định nghĩa L-đầy đủ, phổ biến nhất là phép quy về bậc nhất.

Các vấn đề mở quan trọng nhất liên quan đến L bao gồm câu hỏi có phải L = P, và có phải L = NL.

Lớp liên quan của các bài toán hàm là FL. FL thường được dùng để định nghĩa phép quy về trong không gian lôgarit.

Bài báo năm 2008 của ^[1] của Omer Reingold chứng minh rằng USTCON, bài toán yêu cầu xác định xem hai đỉnh trên đồ thị vô hướng có liên thông không, là trong L, do đó chứng minh rằng L = SL, vì USTCON là SL-đầy đủ.

Một hệ quả là một định nghĩa đơn giản dưới dạng lôgic cho L: nó bao gồm các ngôn ngữ mô tả được bằng lôgic bậc nhất cộng với phép toán lấy bao đóng (trong ngôn ngữ lý thuyết đồ thị, phép toán này biến thành phần liên thông thành một clique).

L là thấp cho chính nó, vì nó có thể giả lập câu hỏi và trả lời cho máy tiên tri dùng không gian lôgarit (nói một cách đơn giản là "phép gọi hàm sử dụng bộ nhớ lôgarit") trong bộ nhớ lôgarit và sử dụng lại cùng bộ nhớ cho nhiều câu hỏi.

Tham khảo

1. Omer Reingold (2008), "Undirected connectivity in log-space", J. ACM, 55 (4)

• Christos Papadimitriou (1993). Computational Complexity (ấn bản thứ 1). Addison Wesley. ISBN 0-201-53082-1. Chương 16: Không gian lôgarit, tr.395–408.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Phần 8.4: Các lớp L và NL, tr.294–296.
• Michael R. Garey và David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. Phần 7.5: Không gian lôgarit, tr.177–181.

Xem thêm

• L/poly, một lớp tương tự như L nhưng không đồng dạng, chứa các chương trình phân nhánh kích thước đa thức.