Mình đang làm một tiểu luận nhỏ về tìm hiểu P và NP chuyên ngành khoa học máy tính, sau một thời gian tìm đọc các tài liệu thì mình vẫn không thể hình dung được bản chất của vấn đề P và NP là gì, bạn nào đã tìm hiểu qua vấn đề này rồi có thể giải thích giúp mình một cách dễ hiểu hai câu hỏi:
Xin cảm ơn các bạn.
P (viết tắt của cụm từ Polynomial Time) và NP (viết tắt của cụm từ Non-deterministic Polynomial Time) với Polynomial Time có thể hiểu là độ phức tạp thuật toán trong thời gian đa thức O($\text{n}^{\text{k}}$), Non-deterministic là không xác định (có thể hiểu là có nhiều khả năng khác nhau có thể xảy ra). Do đó, vấn đề mà P và NP đặt ra đó là liệu rằng tất cả các vấn đề nếu được xác nhận tính đúng đắn trong thời gian đa thức thì nó cũng sẽ giải quyết được trong thời gian đa thức bởi máy tính hay không.
Bài toán P là bài toán có thể giải quyết được và dễ dàng bởi máy tính.
Ví dụ về bài toán thuộc lớp P như sau:
Cho một dãy số nguyên gồm n phần tử và một số nguyên m, hỏi rằng có bao nhiêu số nguyên trong dãy số nguyên n lớn hơn số nguyên m?
Đây là một vấn đề khá đơn giản có thể giải quyết ngay bằng thuật toán máy tính bằng cách cho vòng lặp chạy trong dãy số $n$, với mỗi số nguyên $n_i$, thực hiện so sánh với số nguyên $m$, nếu số nguyên $n_i$ nào lớn hơn số $m$ thì cộng biến đếm lên, do đó độ phức tạp thuật toán dễ dàng được xác định dựa theo số lượng phần tử $n$.
Bài toán NP là bài toán mặc dù đã được xác nhận tính đúng đắn nhưng không thể giải quyết dễ dàng bởi máy tính.
Ví dụ về bài toán thuộc lớp NP như sau:
Cho một dãy số nguyên n và một số nguyên m, hỏi rằng có bao nhiêu cách để tổng của các dãy con trong dãy số nguyên n bằng số nguyên m?
Mặc dù bài toán trên được xác nhận là đúng đắn nhưng nó không thể dễ dàng giải quyết bằng máy tính. Để giải quyết bài toán này, bạn phải thử hết tất cả trường hợp có thể, do đó không có một thuật toán hoặc công thức toán học chính xác nào giúp xác định được rằng trong trường hợp xấu nhất, độ phức tạp thuật toán vẫn nằm trong khoảng phức tạp thời gian đa thức.
Mọi bài toán thuộc lớp P đều thuộc lớp NP, bởi vì một vấn đề nếu được giải quyết được bằng máy tính thì nó cũng hoàn toàn đúng đắn.
Mọi bài toán thuộc lớp NP chưa chắc thuộc lớp P, bởi vì một vấn đề mặc dù đã được xác nhận tính đúng đắn nhưng chưa chắc có thể giải quyết được bằng máy tính một cách dễ dàng.
P $\neq$ NP: Bài toán được xác minh là đúng đắn và có thể có nhiều cách giải quyết khác nhau, do đó chúng ta phải thử hết tất cả các trường hợp có thể, cho nên không thể chắc chắn được rằng chúng ta có thể giải quyết bài toán trong thời gian đa thức cho phép.
P = NP: Bài toán được xác minh là đúng đắn và có cách giải quyết hiệu quả trong thời gian đa thức cho phép.
Đa số các nhà khoa học tin rằng P khác NP, nhưng không thể nào chứng minh được tại sao P khác NP và ngược lại, một số nhà khoa học tin rằng P = NP, nhưng cũng không thể có cách nào chứng minh được, đó là lý do tại sao P và NP là bài toán rất được quan tâm trong giới khoa học và nó được xếp vào 7 bài toán kinh điển mà giải thưởng cho nhà khoa học nào chứng minh được mỗi bài toán đó là 1 triệu USD cộng những huy hiệu cao quý, cho tới thời điểm này chỉ có một bài toán đã chứng minh được đó là giả thuyết Poincaré năm 2002 – 2003 bởi nhà toán học người Nga Grigori Perelman sau khoảng 100 năm tồn tại.
