Bài toán P so với NP

Các bài toán thiên niên kỷ
Giả thuyết Birch và Swinnerton-Dyer Giả thuyết Hodge Bài toán Navier-Stokes Bài toán P so với NP Giả thuyết Poincaré (đã được giải) Giả thuyết Riemann Bài toán Yang-Mills
x t s

Vấn đề mở trong khoa học máy tính: Nếu một bài toán có lời giải có thể kiểm chứng được nhanh chóng, thì có thể tìm lời giải đó nhanh chóng hay không? (các vấn đề mở khác trong khoa học máy tính)

Bài toán P so với NP là một bài toán mở quan trọng trong lý thuyết khoa học máy tính. Mô tả một cách đơn giản, bài toán là có phải bất kì vấn đề nào có lời giải có thể được kiểm chứng "nhanh chóng" cũng có thể được giải một cách "nhanh chóng". Nó được Stephen Cook đưa ra năm 1971 trong bài báo nổi tiếng "The complexity of theorem proving procedures"^[1] và được nhiều người xem là bài toán quan trọng nhất trong ngành.^[2] Nó cũng là một trong số bảy bài toán thiên niên kỷ được chọn bởi Viện Toán học Clay. Mỗi bài trong số bảy bài này có giải thưởng US$1,000,000 cho lời giải đúng đầu tiên.

Cụ thể hơn, cụm từ "nhanh chóng" ở trên được dùng để chỉ thời gian đa thức. Lớp các bài toán có lời giải thực thi trong thời gian đa thức được gọi là "lớp P", hay ngắn gọn hơn là "P". Lớp các bài toán mà lời giải có thể được kiểm tra tính đúng sai trong thời gian đa thức là lớp NP.

Xem xét chẳng hạn bài toán tổng tập hợp con. Đây là một bài toán dễ kiểm tra lời giải nhưng việc tìm lời giải là không đơn giản. Cho một tập hợp các số nguyên, bài toán yêu cầu tìm một tập hợp con khác rỗng có tổng bằng 0. Ví dụ, có tập hợp con nào của {−2, −3, 15, 14, 7, −10} có tổng bằng 0? Lời giải "có, vì {−2, −3, −10, 15} có tổng bằng 0" có thể được kiểm chứng dễ dàng bằng cách cộng các số đó lại. Tuy nhiên, hiện chưa có thuật toán nào để tìm ra một tập hợp như thế trong thời gian đa thức (có một thuật toán đơn giản thực thi trong thời gian hàm mũ là kiểm tra tất cả 2ⁿ-1 tập hợp con khác rỗng). Như vậy, bài toán này nằm trong NP (kiểm chứng nhanh chóng) nhưng chưa biết có nằm trong P (giải nhanh chóng) hay không.

Lời giải của bài toán P = NP sẽ cho biết liệu tất cả các bài toán trong NP, như bài toán tổng tập hợp con, đều có thuật toán thực thi trong thời gian đa thức. Nếu P ≠ NP, thì có nhiều bài toán trong NP (chẳng hạn như các bài toán NP-đầy đủ) có lời giải có thể kiểm chứng được trong thời gian đa thức nhưng không thể tìm ra một lời giải như vậy trong thời gian đa thức.

Tham khảo

1. Cook, Stephen (1971). “The complexity of theorem proving procedures”. Proceedings of the Third Annual ACM Symposium on Theory of Computing. tr. 151–158.
2. Lance Fortnow, The status of the P versus NP problem, Communications of the ACM 52 (2009), số. 9, tr. 78–86. doi:10.1145/1562164.1562186