Karp và bài báo năm 1972 đặt nền móng cho lý thuyết NP-đầy đủ

Bài báo "Reducibility Among Combinatorial Problems" của Richard M. Karp, công bố năm 1972, là một trong những tài liệu có ảnh hưởng sâu rộng nhất trong lịch sử khoa học máy tính. Chỉ với vài chục trang giấy, Karp đã chứng minh rằng hàng loạt bài toán tổ hợp tưởng chừng khác biệt nhau hoàn toàn lại có chung một bản chất tính toán — và đều thuộc lớp NP-đầy đủ.

Bối cảnh: từ câu hỏi lớn đến bước ngoặt

Trước năm 1972, giới nghiên cứu đã biết đến khái niệm bài toán NP-đầy đủ nhờ công trình của Stephen Cook (1971). Cook chứng minh rằng bài toán thỏa mãn biểu thức logic (SAT) là NP-đầy đủ — tức là nếu giải được SAT trong thời gian đa thức thì mọi bài toán thuộc lớp NP đều giải được tương tự.

Tuy nhiên, khi đó nhiều người vẫn coi đây là một kết quả mang tính lý thuyết, khó áp dụng vào thực tế. Câu hỏi đặt ra là: liệu những bài toán mà lập trình viên và kỹ sư gặp hằng ngày có thuộc lớp khó này hay không?

Karp đã trả lời câu hỏi đó một cách dứt khoát.

Phương pháp quy dẫn: chìa khóa của chứng minh

Công cụ cốt lõi trong bài báo là phép quy dẫn đa thức (polynomial-time reduction). Ý tưởng rất trực quan:

• Nếu bài toán A có thể biến đổi thành bài toán B trong thời gian đa thức, ta nói A quy dẫn về B.
• Khi đó, nếu có thuật toán hiệu quả cho B, ta cũng có thuật toán hiệu quả cho A.
• Ngược lại, nếu A đã biết là NP-đầy đủ, thì B cũng NP-đầy đủ.

Bằng cách xây dựng một chuỗi quy dẫn bắt đầu từ SAT, Karp đã "lây lan" tính NP-đầy đủ sang nhiều bài toán khác nhau.

21 bài toán đi vào lịch sử

Trong bài báo, Karp liệt kê và chứng minh tính NP-đầy đủ cho 21 bài toán tổ hợp nổi tiếng, trong đó có nhiều cái tên mà bất kỳ ai học khoa học máy tính cũng từng gặp:

• Bài toán người bán hàng du lịch (Traveling Salesman Problem)
• Bài toán tô màu đồ thị (Graph Coloring)
• Bài toán clique — tìm đồ thị con đầy đủ lớn nhất
• Bài toán phủ tập (Set Cover)
• Bài toán xếp ba lô (Knapsack)
• Bài toán lập lịch công việc (Job Scheduling)
• Bài toán chu trình Hamilton

Điểm đáng chú ý là nhiều bài toán trong số này xuất phát từ những lĩnh vực rất thực tiễn: vận tải, lập lịch sản xuất, thiết kế mạng, tối ưu hóa nguồn lực.

Ý nghĩa sâu xa của kết quả này là: nếu P ≠ NP, thì không có thuật toán hiệu quả nào cho tất cả các bài toán trên. Nói cách khác, độ khó của chúng không phải là vấn đề kỹ thuật tạm thời mà là một giới hạn nội tại của tính toán.

Vì sao bài báo vẫn còn giá trị sau hơn 50 năm?

Kết quả của Karp đã thay đổi cách giới nghiên cứu tiếp cận bài toán tối ưu. Thay vì cố gắng tìm thuật toán chính xác nhanh cho mọi trường hợp, người ta chuyển sang các hướng khác:

• Thuật toán xấp xỉ (approximation algorithms) với tỷ lệ đảm bảo.
• Thuật toán heuristic và metaheuristic như mô phỏng luyện kim, thuật toán di truyền.
• Giải pháp cho các trường hợp đặc biệt hoặc đầu vào có cấu trúc.
• Điện toán song song và phần cứng chuyên dụng để xử lý các bài toán quy mô vừa.

Trong bối cảnh hiện nay, khi các mô hình học máy và trí tuệ nhân tạo ngày càng được dùng để giải các bài toán tổ hợp lớn, hiểu biết về NP-đầy đủ vẫn là nền tảng để đánh giá đúng giới hạn của các phương pháp đó. Các hệ thống như Neural Combinatorial Optimization hay các solver dựa trên học tăng cường đều phải đối mặt với chính những rào cản mà Karp đã chỉ ra.

Với độc giả Việt Nam quan tâm đến khoa học máy tính, bài báo này cũng là tư liệu gốc đáng đọc trong các chương trình đào tạo về thuật toán và lý thuyết tính toán tại các trường đại học.

Đọc bản gốc

Bản PDF của bài báo hiện được lưu trữ công khai và có thể truy cập tại địa chỉ do Đại học Athens cung cấp. Đây là tài liệu ngắn gọn nhưng hàm lượng kỹ thuật cao, phù hợp với người đã có nền tảng về lý thuyết đồ thị và độ phức tạp tính toán.