NL (độ phức tạp)

Trong lý thuyết tính toán, NL (viết tắt của Nondeterministic Logarithmic-space) là một lớp độ phức tạp bao gồm các bài toán quyết định có thể được giải bằng máy Turing không xác định với không gian lưu trữ logarithmic.

Bài toán NL-complete

Một số bài toán được biết đến là NL-complete dựa trên sử dụng không gian lưu trữ logarithmic, bao gồm đồ thị có hướng liên thông và 2-SAT. Bài toán đồ thị có hướng liên thông hỏi xem có đườ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ó thể tìm được một bộ giá trị biến để một biểu thức logic cho trước với mọi điều kiện hai biến được thỏa mãn. Ví dụ về biểu thức này là

(x1 ∨ ¬x3) ∧ (¬x2 ∨ x3) ∧ (¬x1 ∨ ¬x2)

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

NL thuộc lớp P vì có thuật toán đa thức cho bài toán liên thông có hướng ST, tuy nhiên vẫn chưa rõ 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à đã nhận giải Gödel năm 1995 cho công trình này.

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

Giả sử C là một lớp độ phức tạp bao gồm các bài toán giải được bằng máy Turing ngẫu nhiên sử dụng bộ nhớ lôgarit sao cho máy không bao giờ chấp nhận sai nhưng có thể 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ố trạng thái đa thức, nó vẫn có thể sử dụng sự ngẫu nhiên để thoát ra khỏi 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 liệu chúng có bằng nhau hay không.

Dưới đây là một minh chứng đơn giản cho C=NL. Rõ ràng C thuộc về NL vì:

• Nếu dữ liệu không thuộc ngôn ngữ, cả hai đều từ chối tất cả các đường tính toán
• Nếu dữ liệu thuộc 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 thuộc C, ta chọn một thuật toán NL

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ả đồng xu đều ngửa. Sự kiện này xảy ra với xác suất 2, trung bình thuật toán lặp lại 2 lần trước khi dừng. Chỉ cần đếm số đồng xu ngửa, ta chỉ cần bộ nhớ lôgarit.

Vì vậy, khi quan tâm đến lượng bộ nhớ, trong trường hợp này, sự ngẫu nhiên và không xác định dường như bằng nhau.

Ghi chú

Tài liệu tham khảo

• Papadimitriou, C. (1994). “Chương 16: Không gian Logarit”. Độ phức tạp tính toán. Addison-Wesley. ISBN 0-201-53082-1.
• Michael Sipser (1997). “Các mục 8.4–8.6: Các lớp L và NL, NL-completeness, NL bằng coNL”. Giới thiệu về lý thuyết tính toán. PWS Publishing. tr. 294–302. ISBN 0-534-94728-X.
• Giới thiệu về Lý thuyết Độ phức tạp: Bài giảng 7. Oded Goldreich. Đề xuất 6.1. Goldreich gọi lớp C là badRSPACE(log n).