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 của giải 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ả 2n-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.