Những bài toán NP đầy đủ-Đối với nhiều bài toán chúng ta có những giải thuật hữu hiệu để giải, tuy nhiên, có rất nhiều bài toán khác không có giải thuật hữu hiệu để giải | Chương 6 Những bài tóan NP-đầy đủ 1. Giải thuật thòi gian đa thức tất định và không tất định 2. Vấn đề NP-đầy đủ 3. Định lý Cook 4. Một số bài toán NP-đầy đủ 1 Tồn tại hay không tôn tại giải thuật hữu hiệu Đối vói nhiều bài toán chúng ta có những giải thuật hữu hiệu để giải. Tuy nhiên có rất nhiều bài toán khác không có giải thuật hữu hiệu để giải. Và đối vói mt lóp khá lớn của những bài toán như vậy chúng ta không the nói có tôn tại giải thuật hữu hiệu đe giải nó hay không. 2 Những bài toán khó và những bài toán dễ Nhiều nghiên cứu đã được thực hiện và có những cơ chế để phân loại những bài toán mói là khó bằng một số bài toán cũ đã biết. Tuy nhiên đôi khi ranh giói giữa những bài toán khó và những bài toán dễ là khá tế nh. Thí du Dễ Có tồn tại một lối đi tò X đến y mà trong số nh hen M KHó Có tồn tại một lối đi tìr X đến y mà trọng số M Bài toán 1 - BFS - thời gian tuyến tính Bài toán 2 - thòi gian hàm mũ
