Khác biệt giữa bản sửa đổi của “Bài toán P so với NP”
Nội dung được xóa Nội dung được thêm vào
lược dịch từ wiki tiếng Anh |
nKhông có tóm lược sửa đổi |
||
Dòng 1:
{{Vấn đề mở|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?}}
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"<ref>{{Cite book|last=Cook|first=Stephen|authorlink=Stephen Cook|year=1971|chapter=The complexity of theorem proving procedures|chapterurl=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047|title=Proceedings of the Third Annual ACM Symposium on Theory of Computing|pages=151–158}}</ref> và được nhiều người xem là bài toán quan trọng nhất trong ngành.<ref>[[Lance Fortnow]], [http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf ''The status of the '''P''' versus '''NP''' problem''], Communications of the ACM 52 (2009), số. 9, tr. 78–86. {{doi|10.1145/1562164.1562186}}</ref> 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 [[
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ý thuyết độ phức tạp)|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 (độ phức tạp)|NP]]'''.
| |||