NL (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, NL (viết tắt tiếng Anh - Nondeterministic Logarithmic-space) 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 không đơn định bằng bộ nhớ lôgarit.

Bài toán NL-đầy đủ

Một số bài toán được biết là NL-đầy đủ theo phép quy về sử dụng bộ nhớ lôgarit, bao gồm liên thông có hướng ST và 2-SAT. Bài toán liên thông có hướng ST hỏi xem có hay không đường đi từ S đến T trong một đồ thị có hướng. Bài toán 2-SAT hỏi xem liệu có hay không một tập giá trị các biến sao cho một biểu thức logic cho trước với mỗi điều kiện là tuyển của hai biến được thỏa mãn. Chẳng hạn như biểu thức sau

${\displaystyle (x_{1}\vee {\bar {x_{3}}})\wedge ({\bar {x_{2}}}\vee x_{3})\wedge ({\bar {x_{1}}}\vee {\bar {x_{2}}})}$

Quan hệ với các lớp khác

NL nằm trong P do có thuật toán đa thức cho bài toán liên thông có hướng ST, nhưng vẫn chưa biết liệu NL có bằng P và liệu L có bằng NL. Năm 1987, Neil Immerman và Róbert Szelepcsényi đã độc lập chứng minh NL=co-NL (định lý Immerman-Szelepcsényi) và đã được nhận giải Gödel năm 1995 cho công trình này.^[1][2]

Định nghĩa thông qua xác suất

Giả sử C là một lớp độ phức tạp gồm các bài toán giải được bằng máy Turing ngẫu nhiên dùng bộ nhớ lôgarit sao cho máy không bao giờ chấp nhận sai nhưng được phép từ chối sai với xác suất 1/3. Hằng số 1/3 là tùy ý, bất kì số x nào thỏa mãn 0 ≤ x < 1/2 đều chấp nhận được.

Hóa ra C = NL. Có thể thấy C, không như lớp L, không bị giới hạn bởi thời gian đa thức, bởi vì mặc dù nó chỉ có một số đa thức các trạng thái, nó cũng có thể dùng sự ngẫu nhiên để thoát ra một vòng lặp vô hạn. Nếu giới hạn trong thời gian đa thức, ta nhận được lớp RL nằm trong NL nhưng không biết có bằng hay không.

Sau đây là một chứng minh đơn giản cho C=NL. Rõ ràng C nằm trong NL do:

• Nếu dữ liệu vào không nằm trong ngôn ngữ, cả hai đều từ chối tất cả các đường tính toán
• Nếu dữ liệu vào nằm trong ngôn ngữ, thuật toán NL chấp nhận ít nhất một đường tính toán trong khi thuật toán C chấp nhận 2/3 số đường tính toán.

Để chứng minh NL nằm trong C, ta lấy một thuật toán NL và chọn một đường tính toán bất kì có độ dài n, và lặp lại 2ⁿ lần. Do không có đường tính toán nào có độ dài lớn hơn n, và có tất cả 2ⁿ đường tính toán, xác suất tìm được một đường được chấp nhận là cao (chặn dưới bởi một hằng số).

Có một vấn đề là ta không có đủ bộ nhớ để đếm đến 2. Để vượt qua trở ngại này, ta sử dụng một thuật toán đếm ngẫu nhiên: tung n đồng xu và dừng khi tất cả đều ngửa. Do sự kiện này xảy ra với xác suất 2^-n, trung bình thuật toán lặp lại 2ⁿ lần trước khi dừng. Do chỉ cần đếm số đồng xu ngửa, ta chỉ cần bộ nhớ lôgarit.

Do đó, khi ta chỉ quan tâm đến lượng bộ nhớ, trong trường hợp này, có vẻ như sự ngẫu nhiên và không đơn định là mạnh ngang nhau.

Ghi chú

1. N. Immerman (1988). “Nondeterministic space is closed under complementation”. SIAM Journal on Computing. 17: 935–938.
2. R. Szelepcsényi (1988). “The method of forced enumeration for nondeterministic automata”. Acta Informatica. Springer-Verlag New York, Inc. 26 (3): 279–284. doi:10.1007/BF00299636.

Tài liệu thao khảo

• 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. tr. 294–302. ISBN 0-534-94728-X.
• Introduction to Complexity Theory: Lecture 7. Oded Goldreich. Proposition 6.1. Goldreich gọi lớp C ở trên là badRSPACE(log n).