Mở đầu về bài toán P và NP
P vs. NP (có thể được viết là P = NP) là một bài toán chưa được giải trong toán học cũng như khoa học máy tính. Đây là một trong 7 bài toán thiên niên kỷ được viện toán học Clay chọn ra. Bất cứ bài toán nào trong số 7 bài toán này đều có giải thưởng $1,000,000 cho người đầu tiên giải được.
Bài toán P vs. NP (Polynomial versus Nondeterministic Polynomial) là một bài toán được đưa ra bởi Leonid Levin và Stephen Cook vào năm 1971. Nói một cách đơn giản, bài toán này là câu hỏi: với bất cứ vấn đề nào mà lời giải của nó được kiểm chứng một cách nhanh chóng, liệu chúng ta có thể tìm ra lời giải đó một cách nhanh chóng được hay không?
Phân tích
“Nhanh chóng” ở đây được hiểu là có thể hoàn thành trong thời gian đa thức. Thời gian đa thức cũng là một khái niệm phức tạp của toán học và khoa học máy tính, có liên quan đến độ phức tạp của thuật toán. Một thuật toán được gọi là hoàn thành trong thời gian đa thức, nếu số bước thực thi của thuật toán đó cho tới khi tìm ra lời giải là O(n^k) với k > 0, trong đó n là độ phức tạp của đề bài.
Các phép toán cơ bản cộng trừ nhân chia, luỹ thừa, logarithm đều được thực hiện trong thời gian đa thức. Những thuật toán thực thi trong thời gian đa thức được coi là thực thi nhanh chóng, vì khi độ phức tạp đầu vào tăng lên, thời gian để tìm ra lời giải cũng tăng lên, nhưng tăng từ từ.
Ngược lại, một số thuật toán không hoàn thành trong thời gian đa thức là hoàn thành chậm. Ví dụ một thuật toán hoàn thành trong thời gian hàm mũ chẳng hạn O(3^n), thì khi đầu vào phức tạp hơn, thời gian để tìm ra lời giải sẽ tăng rất nhanh. Với trường hợp trên, nếu n tăng gấp đôi thì thời gian sẽ tăng gấp 9 lần, nếu n tăng gấp 4 thì thời gian sẽ tăng gấp 81 lần, n tăng gấp 8 thì thời gian sẽ tăng gấp 6561 lần, v.v… Một tốc độ tăng rất khủng khiếp.
Quay trở lại với bài toán P vs. NP. P là tập hợp các bài toán mà lời giải của nó có thể được tìm ra trong thời gian đa thức, còn NP là tập hợp các bài toán mà lời giải có thể được kiểm tra trong thời gian đa thức.
Ví dụ
Xét một ví dụ về bài toán NP như sau:
Cho một tập hợp các số nguyên, yêu cầu tìm ra một tập con khác rỗng có tổng bằng 0. Ví dụ với đầu vào là {-2, -3, 14, 15, 7, -10} chúng ta có một lời giải là {-2, -3, -10, 15}. Đây là một bài toán mà lời giải của nó rất dễ kiểm chứng (chỉ cần cộng các số đó lại với nhau), nhưng lời giải đó lại không dễ dàng tìm ra được. Ít nhất là hiện nay chưa có một thuật toán nào có thể tìm ra lời giải bài toán này trong thời gian đa thức. Thuật toán đơn giản nhất để tìm ra lời giải là thử tất cả các tập con của đầu vào, nhưng thuật toán này có thời gian hoàn thành là hàm mũ.
Câu hỏi đặt ra liệu có tồn tại một thuật toán tìm ra lời giải bài toán này trong thời gian đa thức hay không? Đó cũng là vấn đề lớn nhất của bài toán P vs. NP, mối quan hệ của P và NP thực sự là gì. Đương nhiên là P và NP có giao nhau, tức là có những bài toán vừa nhanh chóng kiểm chứng được lời giải, vừa nhanh chóng tìm ra được lời giải đó.
Nếu P = NP có nghĩa là tất cả các bài toán trong NP, bao gồm bài toán tổng tập con ở trên, đều có thể được giải trong thời gian đa thức (dù chưa tìm ra thuật toán nhưng về lý thuyết là có tồn tại). Nếu P ≠ NP thì nhiều bài toán trong NP, dù lời giải rất dễ kiểm chứng thì có nhiều bài toán trong NP 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.
Mối quan hệ của P và NP đã được đặt ra bởi Godel vào năm 1956 trong một bức thư gửi Von Neumann. Nhưng bài toán mới được chú ý vào năm 1971, khi Cook và Levin chứng minh được rằng, trong NP có những bài toán gọi là NP-complete (bài toán NP đầy đủ). Đây là bài toán khó nhất trong số các bài toán NP, mọi bài toán khác thuộc NP đều có thể đưa về bài toán NP-complete trong thời gian đa thức.
Chỉ cần một bài toán NP-complete có thể giải được trong thời gian đa thức, thì mọi bài toán NP cũng sẽ giải được trong thời gian đa thức, khi đó P = NP. Nhưng đáng tiếc, hiện nay thuật toán để giải các bài toán này vẫn chưa có (và cũng chưa biết là nó có tồn tại hay không).
Vì vậy, hiện tại, bài toán P vs. NP có thể có những hướng sau:
P = NP và một lúc nào đó sẽ có người chứng minh điều này.
P ≠ NP và một lúc nào đó sẽ có người chứng minh điều này.
P ≠ NP nhưng sẽ không bao giờ có ai chứng minh được (hình dung rằng bài toán chứng minh P ≠ NP cũng là một bài toán NP, nếu có lời giải thì có thể kiểm chứng nhanh chóng, nhưng tìm ra lời giải thì đời này qua đời khác).
P = NP nhưng sẽ không bao giờ có người chứng minh được điều này.
Vấn đề P vs. NP sẽ mãi mãi không có lời giải, tức là không thể chứng minh được mối quan hệ giữa hai tập hợp này.
(To be continue…)
