NP-Hoàn chỉnh và Tính không thể giải quyết

NP-hoàn chỉnh xác định các bài toán khó nhất trong lớp NP — những bài toán mà mọi bài toán NP đều quy về được — và cung cấp khuôn khổ tiêu chuẩn để nhận diện các bài toán mà chưa có hoặc khó có thuật toán hiệu quả nào được biết đến.

Definition

Một bài toán quyết định là NP-hoàn chỉnh nếu nó thuộc NP (các trường hợp 'có' của nó có các chứng chỉ có thể kiểm chứng hiệu quả) và mọi bài toán trong NP đều quy về nó trong thời gian đa thức; những bài toán như vậy là khó nhất trong NP, và một thuật toán thời gian đa thức cho bất kỳ bài toán nào trong số đó sẽ mang lại một thuật toán cho tất cả.

Scope

Chủ đề này bao gồm các lớp phức tạp P và NP, phép quy dẫn thời gian đa thức, định nghĩa về NP-khó và NP-hoàn chỉnh, định lý Cook-Levin thiết lập tính thỏa mãn là NP-hoàn chỉnh, danh mục các bài toán NP-hoàn chỉnh của Karp, và những hệ quả thực tiễn của tính không thể giải quyết đối với thiết kế thuật toán. Nó áp dụng các khái niệm này để nhận diện và đối phó với các bài toán khó; lý thuyết hình thức rộng hơn về các lớp phức tạp tính toán được đề cập trong lĩnh vực con lý thuyết tính toán.

Core questions

• Điều gì phân biệt các lớp phức tạp P và NP?
• Phép quy dẫn thời gian đa thức chuyển độ khó từ bài toán này sang bài toán khác như thế nào?
• Định lý Cook-Levin thiết lập điều gì, và tại sao tính thỏa mãn lại là trung tâm?
• Một bài toán mới được chứng minh là NP-hoàn chỉnh bằng cách quy dẫn từ một bài toán đã biết như thế nào?
• Khi một bài toán được chứng minh là NP-khó, những chiến lược thuật toán nào còn lại?

Key concepts

• lớp phức tạp P
• lớp phức tạp NP
• phép quy dẫn thời gian đa thức
• NP-khó
• NP-hoàn chỉnh
• định lý Cook-Levin
• tính thỏa mãn Boolean (SAT)
• vấn đề P so với NP

Key theories

Định lý Cook-Levin

Định lý Cook-Levin chứng minh rằng tính thỏa mãn Boolean (SAT) là NP-hoàn chỉnh: mọi bài toán trong NP đều quy về nó trong thời gian đa thức, cung cấp bài toán NP-hoàn chỉnh đầu tiên và là điểm tựa để chứng minh các bài toán khác là khó.

Tính quy dẫn giữa các bài toán tổ hợp

Karp đã chỉ ra rằng các phép quy dẫn thời gian đa thức liên kết nhiều bài toán tự nhiên — clique, tập phủ đỉnh, chu trình Hamilton, phân hoạch và các bài toán khác — thành một mạng lưới các bài toán NP-hoàn chỉnh, do đó mỗi bài toán có thể được chứng minh là khó bằng cách quy dẫn từ một bài toán khác.

Clinical relevance

Việc nhận ra một bài toán là NP-hoàn chỉnh là một trong những kết quả hữu ích nhất trong khoa học máy tính: nó cho các kỹ sư biết không nên mong đợi một thuật toán chính xác nhanh chóng và thay vào đó nên triển khai các thuật toán xấp xỉ, thuật toán heuristic, các bộ giải chính xác được điều chỉnh cho các trường hợp điển hình, hoặc giới hạn trong các trường hợp đặc biệt có thể giải quyết được. Nhiều bài toán lập lịch, định tuyến, đóng gói và thiết kế là NP-hoàn chỉnh.

History

Stephen Cook đã giới thiệu NP-hoàn chỉnh vào năm 1971, chứng minh SAT là NP-hoàn chỉnh; Leonid Levin đã đạt được những kết quả tương tự một cách độc lập. Bài báo năm 1972 của Richard Karp đã chỉ ra 21 bài toán tự nhiên là NP-hoàn chỉnh, thiết lập phạm vi của khuôn khổ này. Cuốn sách năm 1979 của Garey và Johnson đã lập danh mục hàng trăm bài toán NP-hoàn chỉnh và trở thành tài liệu tham khảo tiêu chuẩn.

Debates

P so với NP

Liệu P có bằng NP hay không — liệu mọi bài toán có thể kiểm chứng hiệu quả cũng có thể giải quyết hiệu quả hay không — là vấn đề mở hàng đầu trong lĩnh vực này; hầu hết các nhà nghiên cứu đều phỏng đoán P không bằng NP, nhưng câu hỏi này vẫn chưa được giải quyết và là một bài toán Giải thưởng Thiên niên kỷ.

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

Sự khác biệt giữa NP-khó và NP-hoàn chỉnh là gì?

Một bài toán là NP-khó nếu mọi bài toán NP đều quy về nó trong thời gian đa thức, nhưng bản thân nó không nhất thiết phải nằm trong NP và không nhất thiết phải là một bài toán quyết định. Một bài toán là NP-hoàn chỉnh nếu nó vừa là NP-khó vừa nằm trong NP. Các bài toán NP-hoàn chỉnh là những bài toán khó nhất vẫn nằm trong NP.

NP-hoàn chỉnh có nghĩa là một bài toán không bao giờ có thể được giải quyết không?

Không. Nó có nghĩa là không có thuật toán thời gian đa thức nào được biết đến cho tất cả các đầu vào và có khả năng không tồn tại nếu P không bằng NP. Trong thực tế, những bài toán như vậy được giải quyết bằng các thuật toán xấp xỉ, thuật toán heuristic, các bộ giải thời gian lũy thừa hoạt động trên các trường hợp thực tế, hoặc bằng cách giới hạn trong các trường hợp đặc biệt.