Bài giảng Thuật toán nâng cao - Chương 10: Lớp các bài toán NP đầy đủ - Nguyễn Thanh Bình

Định nghĩa

Lớp độ phức tạp p (polynomial time) được định nghĩa gồm các bài toán quyết định được giải quyết bởi thời gian đa thức

nghĩa là tồn tại các thuật toán có độ phức tạp hàm đa thức giải quyết bài toán

Phần lớn các bài toán chúng ta đã xem xét là bài toán p

Bài giảng Thuật toán nâng cao - Chương 10: Lớp các bài toán NP đầy đủ - Nguyễn Thanh Bình trang 1

Bài giảng Thuật toán nâng cao - Chương 10: Lớp các bài toán NP đầy đủ - Nguyễn Thanh Bình trang 2

Bài giảng Thuật toán nâng cao - Chương 10: Lớp các bài toán NP đầy đủ - Nguyễn Thanh Bình trang 3

Bài giảng Thuật toán nâng cao - Chương 10: Lớp các bài toán NP đầy đủ - Nguyễn Thanh Bình trang 4

Bài giảng Thuật toán nâng cao - Chương 10: Lớp các bài toán NP đầy đủ - Nguyễn Thanh Bình trang 5

Tải về để xem đầy đủ hơn

10 trang | Chia sẻ: cucnt | Lượt xem: 488 | Lượt tải: 0

File đính kèm: