Lý thuyết độ phức tạp tính toán
Lê Công Thành
Cuốn sách này chia thành 6 chương, trong đó Chương ) là chương mở đầu nhằm giới thiệu khái quát về lý thuyết độ phức tạp tính toán và trình bày một cách tiếp cận thích hợp các bài toán thuộc nhiều lĩnh vực khác nhau, tạo tiền đề cho việc giải các bài toán ấy trên cùng một mô hình tính toán tổng quát, mô hình máy Turing cũng như việc phân chúng thành những lớp phức tạpChương 1 nghiên cứu máy Turing và các biến thể chính của nó, chủ yếu là khảo sát khả năng đoán nhận ngôn ngữ của máy, nhằm lý giải tại sao máy Turing được chọn làm mô hình tính toán tổng quát
Chương 2, 3 tiến hành khảo sát độ phức tạp thời gian và độ phức tạp không gian của thuật toán, thực hiện phân lớp các bài toán theo độ phức tạp của các thuật toán giải chúng.
Trong Chương 4 thiết lập trật tự thời gian và trật tự không gian đối với các lớp phức tạp nhằm chứng tỏ tính nan giải của nhiều bài toàn.
Chương 5 dành để giới thiệu các hướng nghiên cứu mà có khả năng mang lại những giải pháp tích cực đối với các vấn đề nảy sinh, đặc biệt trong hoạt động thực tiễn