Lý thuyết tính toán và sự phức tạp tính toán

Trong bài này, tôi sẽ duyệt qua các ý tưởng lớn và lịch sử xoay quanh một trong những bài toán quan trọng nhất của thế kỷ 21: bài toán “P chọi NP” (P versus NP). Câu trả lời đáng giá 1 triệu USD và danh tiếng đi vào lịch sử khoa học. Cũng như bài toán Fermat lớn, bản thân câu trả lời cho bài “P chọi NP” không hẳn quan trọng bằng các kỹ thuật, hướng nghiên cứu, ngành nghiên cứu mới mà người ta khám phá ra để đi đến câu trả lời.
Quan trọng hơn hết, tôi hy vọng bài này đóng vai trò giới thiệu và khích lệ các bạn đến với một nhánh trung tâm của khoa học máy tính: lý thuyết tính toán và sự phức tạp (computational and complexity theory). Hành trình của ta sẽ ghé qua những vấn đề căn bản nhất mang đậm tính triết học của khoa học máy tính.

Chi tiết bài báo: Chung Quy Chỉ Tại Cantor

https://www.cse.buffalo.edu//~hungngo/Vietnamese/cantor.pdf