Bài giảng Thiết kế và Phân tích thuật toán_Chương 7: Các bài toán NP-Khó và NP-Đầy đủ

Chúng ta đã biết nhiều bài toán, điển hình là bài toán người bán hàng, bài toán ba lô, bài toán chu trình Hamilton,... Các thuật toán tốt nhất để giái quyết các bài toán này đều có thời gian chạy không phải là thời gian đa thức, chẳng hạn thuật toán quy hoạch động cho bài toán người bán hàng có thời gian chạy 0(n2),... Cho tới nay chưa có ai tìm ra được thuật toán thời gian đa thức cho bất kỳ bài toán nào trong lớp các bài toán trên. Vấn đề đặt ra là có tồn tại hay không thuật toán thời gian chạy đa thức cho cac bài toán trên?