NP-Hoàn chỉnh và Phép quy giản

Một bài toán NP-hoàn chỉnh là một trong những bài toán khó nhất trong lớp NP, theo nghĩa là mọi bài toán NP đều có thể quy giản về nó một cách hiệu quả, do đó việc giải nhanh bất kỳ bài toán NP-hoàn chỉnh nào cũng sẽ giải quyết được tất cả các bài toán khác.

Definition

Một bài toán là NP-hoàn chỉnh nếu nó thuộc NP và mọi bài toán trong NP đều có thể quy giản về nó bằng một phép quy giản trong thời gian đa thức; những bài toán như vậy là các thành viên khó nhất của NP, tương đương với nhau thông qua các phép biến đổi hiệu quả.

Scope

Chủ đề này bao gồm lớp NP của các bài toán có thể kiểm chứng trong thời gian đa thức, các phép quy giản một-nhiều trong thời gian đa thức, đị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 tổ hợp NP-hoàn chỉnh của Karp, và phương pháp chứng minh các bài toán mới là NP-hoàn chỉnh bằng cách quy giản từ các bài toán đã biết.

Core questions

• Điều gì có nghĩa khi một bài toán nằm trong số những bài toán khó nhất trong NP?
• Định lý Cook–Levin xác định bài toán NP-hoàn chỉnh đầu tiên như thế nào?
• Các phép quy giản được sử dụng như thế nào để chứng minh một bài toán mới là NP-hoàn chỉnh?
• Tại sao tính NP-hoàn chỉnh của một bài toán lại có ý nghĩa đối với hàng nghìn bài toán khác?

Key theories

Định lý Cook–Levin

Tính thỏa mãn Boolean là NP-hoàn chỉnh vì phép tính của bất kỳ bộ kiểm chứng thời gian đa thức nào cũng có thể được mã hóa thành một trường hợp thỏa mãn, cung cấp bài toán hoàn chỉnh nền tảng từ đó các bài toán khác được suy ra.

Các phép quy giản của Karp và mạng lưới các bài toán NP-hoàn chỉnh

Karp đã chỉ ra rằng hai mươi mốt bài toán tự nhiên, từ tô màu đồ thị đến bài toán quyết định người bán hàng rong, là NP-hoàn chỉnh bằng các phép quy giản thời gian đa thức, khởi đầu thực tiễn thiết lập độ khó thông qua một mạng lưới quy giản ngày càng phát triển.

Clinical relevance

NP-hoàn chỉnh là một chẩn đoán thực tế về tính không thể giải quyết được: một khi một bài toán trong lập kế hoạch, hậu cần, thiết kế hoặc kiểm chứng được chứng minh là NP-hoàn chỉnh, các kỹ sư sẽ ngừng tìm kiếm một thuật toán chính xác nhanh chóng được đảm bảo và chuyển sang các thuật toán xấp xỉ, các phương pháp heuristic, các bộ giải lập trình số nguyên, hoặc các ràng buộc làm cho bài toán trở nên khả thi.

History

Cook đã chứng minh tính thỏa mãn là NP-hoàn chỉnh vào năm 1971, và Levin độc lập đạt được các kết quả tương đương ở Liên Xô. Năm 1972, Karp đã chứng minh thêm hai mươi mốt bài toán NP-hoàn chỉnh khác, cho thấy sự phổ biến của hiện tượng này và biến NP-hoàn chỉnh thành công cụ trung tâm để chẩn đoán độ khó tính toán.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

NP là viết tắt của từ gì?

NP có nghĩa là thời gian đa thức không xác định (nondeterministic polynomial time). Tương đương, một bài toán thuộc NP nếu một giải pháp được đề xuất có thể được kiểm tra trong thời gian đa thức, ngay cả khi việc tìm ra nó có vẻ khó khăn. Tuyến đường của người bán hàng rong dưới một độ dài nhất định rất dễ kiểm tra khi đã có, nhưng rõ ràng là khó khám phá.

Làm thế nào để chứng minh một bài toán mới là NP-hoàn chỉnh?

Bạn cần chứng minh hai điều: rằng bài toán đó thuộc NP, do đó các giải pháp ứng cử viên có thể được kiểm tra nhanh chóng, và rằng một bài toán NP-hoàn chỉnh đã biết có thể quy giản về nó trong thời gian đa thức. Phép quy giản này chuyển giao độ khó đã biết, đặt bài toán mới vào nhóm những bài toán khó nhất trong NP.