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

Bài toán P so với NP đặt ra câu hỏi liệu mọi bài toán mà lời giải của chúng có thể được kiểm chứng nhanh chóng thì cũng có thể được giải quyết nhanh chóng hay không. Đây là một câu hỏi mở trọng tâm của khoa học máy tính lý thuyết và là một trong các bài toán Giải thưởng Thiên niên kỷ của Viện Clay.

Definition

P là lớp các bài toán có thể giải được trong thời gian đa thức, và NP là lớp các bài toán mà các lời giải đề xuất của chúng có thể kiểm chứng được trong thời gian đa thức; bài toán P so với NP hỏi liệu hai lớp này có bằng nhau hay không, điều này đúng khi và chỉ khi một số bài toán NP-đầy đủ có thể giải được trong thời gian đa thức.

Scope

Chủ đề này bao gồm phát biểu chính thức của P so với NP, sự tương đương của nó với việc liệu bất kỳ bài toán NP-đầy đủ nào có thuật toán thời gian đa thức hay không, những hệ quả của cả hai câu trả lời, các rào cản như tương đối hóa, chứng minh tự nhiên và đại số hóa đã cản trở tiến bộ, và giả thuyết phổ biến rằng các lớp này khác nhau.

Core questions

• Việc tìm kiếm một giải pháp có khó hơn về cơ bản so với việc kiểm tra một giải pháp không?
• Tại sao câu trả lời lại phụ thuộc vào việc liệu bất kỳ bài toán NP-đầy đủ nào có thuộc P hay không?
• Thế giới sẽ trông như thế nào nếu P bằng NP, và nếu không?
• Tại sao hàng thập kỷ nỗ lực đã không giải quyết được câu hỏi này?

Key theories

Sự tương đương với NP-đầy đủ

P bằng NP khi và chỉ khi bất kỳ bài toán NP-đầy đủ nào có thuật toán thời gian đa thức, do đó câu hỏi rộng lớn này quy về tính khả thi của một bài toán cụ thể duy nhất như bài toán thỏa mãn.

Các rào cản chứng minh

Các kết quả về tương đối hóa, chứng minh tự nhiên và đại số hóa cho thấy các kỹ thuật chứng minh chính đã biết không thể giải quyết bài toán P so với NP, điều này giải thích sự khó khăn và hướng dẫn việc tìm kiếm các phương pháp hoàn toàn mới.

Clinical relevance

Sự bất bình đẳng được giả định giữa P và NP là giả định làm việc đằng sau việc coi các bài toán NP-khó là không thể giải quyết được và đằng sau tính bảo mật của mật mã học, vì việc giải quyết hiệu quả các bài toán NP sẽ phá vỡ các phương pháp mã hóa được sử dụng rộng rãi; một bằng chứng mang tính xây dựng rằng P bằng NP sẽ làm thay đổi tối ưu hóa, hậu cần và khoa học.

History

Cook đã đặt ra câu hỏi này vào năm 1971 cùng với NP-đầy đủ, và nó nhanh chóng được công nhận là cơ bản. Các nỗ lực thông qua các giới hạn dưới của mạch vào những năm 1980 đã gặp phải rào cản chứng minh tự nhiên được Razborov và Rudich xác định, và vào năm 2000, Viện Toán học Clay đã đặt tên nó là một bài toán Giải thưởng Thiên niên kỷ với giải thưởng một triệu đô la.

Debates

Liệu bài toán P so với NP có bao giờ được giải quyết, và câu trả lời là gì?

Hầu hết các nhà nghiên cứu đều giả định rằng P không bằng NP, nhưng không có bằng chứng nào tồn tại và các kỹ thuật đã biết được chứng minh là không đủ. Các ý kiến khác nhau về việc liệu việc giải quyết đã gần kề, có cần toán học hoàn toàn mới hay không, hoặc liệu câu hỏi này thậm chí có thể độc lập với các tiên đề tiêu chuẩn hay không.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp
• Alexander Razborov

Seminal works

• cook1971
• aroraBarak2009

Frequently asked questions

Điều gì sẽ xảy ra nếu P bằng NP?

Nhiều bài toán hiện được cho là không thể giải quyết được, từ lập lịch tối ưu đến phá vỡ các mã mật mã, sẽ có các thuật toán hiệu quả, và hành động tìm kiếm giải pháp sẽ không khó hơn việc kiểm tra chúng. Các tác động đến thương mại, an ninh và khoa học sẽ rất sâu sắc, đây là một phần lý do tại sao hầu hết các chuyên gia đều kỳ vọng P không bằng NP.

Tại sao bài toán này lại khó giải quyết đến vậy?

Việc chứng minh P bằng NP đòi hỏi một thuật toán nhanh cho một bài toán NP-đầy đủ, điều mà chưa ai tìm thấy; việc chứng minh chúng khác nhau đòi hỏi phải chỉ ra rằng không thể tồn tại một thuật toán như vậy. Các kết quả về tương đối hóa và chứng minh tự nhiên cho thấy các kỹ thuật tiêu chuẩn vốn dĩ không thể thiết lập điều thứ hai, vì vậy cần một cách tiếp cận thực sự mới.