NP-đầy đủ

Trong lý thuyết độ phức tạp tính toán, lớp NP-đầy đủ là một lớp các bài toán quyết định. Một bài toán L là NP-đầy đủ nếu nó nằm trong lớp NP (lời giải cho L có thể được kiểm chứng trong thời gian đa thức) và là NP-khó (mọi bài toán trong NP đều có thể quy về L trong thời gian đa thức).

Mặc dù bất kì lời giải nào cho mỗi bài toán đều có thể được kiểm chứng nhanh chóng, hiện chưa có cách nào tìm ra được lời giải đó một cách hiệu quả. Thời gian thực thi của tất cả các thuật toán hiện tại cho những bài toán này đều tăng rất nhanh theo kích thước bài toán. Vì vậy ngay cả những trường hợp có kích thước tương đối lớn đã đòi hỏi thời gian hàng tỷ năm để giải. Do đó, việc xác định xem những bài toán này có thể được giải quyết nhanh chóng hay không (thường gọi là bài toán P so với NP) là một trong những bài toán mở của khoa học máy tính hiện nay.

Các bài toán NP-đầy đủ xuất hiện thường xuyên trong thực tế nên, mặc dù chưa có giải thuật trong thời gian đa thức cho chúng, các nhà nghiên cứu vẫn tìm cách giải quyết chúng thông qua các phương pháp khác như thuật toán xấp xỉ, nhân tử hóa, v.v...

Tổng quan

Lớp NP-đầy đủ là tập hợp các bài toán NP-khó trong NP.

Lớp NP-đầy đủ được quan tâm nghiên cứu bởi khả năng kiểm chứng nhanh chóng lời giải (NP) dường như có liên hệ với khả năng tìm kiếm nhanh chóng lời giải (P). Hiện vẫn chưa biết được nếu mọi bài toán trong NP đều có thể được giải quyết nhanh chóng hay không (đây chính là bài toán P so với NP). Tuy nhiên, nếu bất kì một bài toán nào trong NP-đầy đủ có thể được giải quyết nhanh chóng, thì theo định nghĩa của NP-đầy đủ, mọi bài toán trong NP đều có thể được giải quyết nhanh chóng.

Lịch sử

Khái niệm NP-đầy đủ được đưa ra bởi Stephen Cook năm 1971 trong bài báo mang tên "The complexity of theorem-proving procedures".^[1] Tuy nhiên tên gọi NP-đầy đủ không xuất hiện trong bài báo này mà được đưa ra sau này. Trong đó Cook đã chứng minh định lý Cook-Levin (Leonid Levin cũng chứng minh định lý này một cách độc lập cùng thời gian với Cook). Định lý này chứng minh bài toán Circuit-SAT là NP-đầy đủ. Năm 1972, Richard Karp chứng minh 21 bài toán khác cũng là NP-đầy đủ.^[2]. Từ sau đó đến nay, hàng nghìn bài toán đã được chứng minh là NP-đầy đủ. Nhiều bài toán quan trọng trong số đó được liệt kê trong cuốn "Computers and Intractability: A Guide to the Theory of NP-Completeness" của Garey và Johnson.^[3]

Ví dụ

Sau đây là một số bài toán NP-đầy đủ thường gặp:

• Bài toán xếp ba lô
• Bài toán người bán hàng
• Cây Steiner nhỏ nhất
• Chu trình Hamilton
• Bài toán tập đỉnh độc lập
• Clique
• Bài toán thỏa mãn công thức logic
• Bài toán đồ thị con đẳng cấu
• Bài toán tô màu đồ thị

Giải quyết bài toán NP-đầy đủ

Hiện nay mọi thuật toán cho các bài toán NP-đầy đủ đều đòi hỏi thời gian lớn hơn đa thức của kích thước dữ liệu vào, và cũng không rõ liệu có tồn tại thuật toán nhanh hơn hay không.

Các phương pháp sau đây thường được áp dụng để giải quyết các bài toán tính toán nói chung, và trong nhiều trường hợp dẫn đến thuật toán nhanh hơn.

• Thuật toán xấp xỉ: Thay vì tìm kiếm lời giải tối ưu, chỉ cần tìm một lời giải "gần" tối ưu.
• Thuật toán ngẫu nhiên: Sử dụng bit ngẫu nhiên để giảm thời gian chạy trung bình, và cho phép thuật toán thất bại với một xác suất nhỏ (xem phương pháp Monte Carlo)
• Hạn chế: giải quyết một số trường hợp đặc biệt của dữ liệu vào bằng các thuật toán đặc biệt cho các trường hợp đó (ví dụ như đồ thị phẳng, điểm trong không gian Euclide).
• Độ phức tạp tham số: đưa ra thêm một số tham số, nếu trong trường hợp đặc biệt các tham số này là nhỏ thì thời gian chạy cũng nhanh hơn.
• Heuristic: có những thuật toán làm việc khá tốt trong nhiều trường hợp nhưng chưa thể chứng minh được chúng luôn cho kết quả tốt trong mọi trường hợp.

Ghi chú

1. Cook, S.A. (1971). “The complexity of theorem proving procedures”. Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. tr. 151–158. doi:10.1145/800157.805047.
2. Richard M. Karp (1972). “Reducibility Among Combinatorial Problems”. Trong R. E. Miller and J. W. Thatcher (biên tập). Complexity of Computer Computations. New York: Plenum. tr. 85–103. Liên kết ngoài trong |chapter= (trợ giúp)
3. M.R. Garey & Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.