Category Archives: Lý thuyết tính toán

Bài toán nào nằm trong P được xem là bài toán “dễ”, còn lại là các bài toán khó. Lớp P chỉ có thể được định nghĩa chính xác bằng toán học nếu ta có một mô hình toán học cho khái niệm giải thuật. Dĩ nhiên mô hình này không gì khác hơn là [...]

“Các bài toán có và không có các giải thuật tốt để giải đều rất đáng quan tâm … Tôi giả định (conjecture) rằng không có giải thuật tốt nào để giải bài toán chàng bán hàng rong (traveling salesman). Các lý do của tôi cũng giống như lý do cho các giả định toán [...]

“Tầm mắt của chúng ta chẳng xa gì lắm, mà ta đã thấy bao nhiêu việc để làm.” [Alan Turing - 1950] Việc ai đó có tin là Church đã giải được entscheidungsproblem hay không phụ thuộc vào việc người đó có tin rằng giải tích lambda thật sự bao gồm những gì tính toán [...]

“Không. Hồi đó khoa Triết Học không có ai quan tâm đến mấy thứ ấy.” [Alonzo Church trả lời khi được hỏi có quan hệ gì giữa khoa Toán và khoa Triết ở Princeton thời cuối 1920, đầu 1930.] Bản chất của bài toán Hilbert số 10 nằm ở các câu hỏi: “các hàm nào [...]

“Tôi đã khám phá ra một khả năng logic và hợp pháp mà hợp chủng quốc Hoa Kỳ có thể biến thành một nước độc tài.” [Trích lời Gödel nói với Oskar Morgenstern năm 1952] Đầu thế kỷ 20, Hilbert dành rất nhiều thời gian phát triển “chương trình Hilbert” như đã đề cập. Tại [...]

“Nếu tôi có một số thành công nhất định trong toán học thì đó là vì tôi luôn thấy nó rất khó.” [Trích lời Hilbert nói với Harald Bohr (1887-1951)] Năm 1900, tại hội nghị các nhà toán học thế giới ở Paris (International Congress of Mathematicians), David Hilbert đề nghị 23 bài toán làm [...]

Trong bài trước, ta đã chứng minh |S|< |2^S| với mọi tập S bằng lý luận đường chéo. Cantor không dừng lại ở đó, ông xét một chuỗi vô hạn các lực lượng của các tập vô hạn được tạo ra theo cách này: |N|, |2N|, |22^N|, …, và ông dùng Aleph không, Aleph một, [...]

Tôi thấy, nhưng tôi không tin. [Trích một bức thư Cantor gửi Dedekind năm 1878] Trở lại với hành trình lịch sử của ta: trong các thập niên cuối cùng cùng của thế kỷ 19, nhà toán học vĩ đại Georg Cantor (Georg Ferdinand Ludwig Philipp Cantor, 1845-1918) đề ra một trong những tư tưởng [...]

Giả sử bạn đi làm cho một công ty nào đó, xếp giao nhiệm vụ viết một chương trình tốt, chạy nhanh, để giải một bài toán loại rất khó này, bạn sẽ làm gì? Ta thử ghi ra đây vài khả năng: Hỏi giáo sư dạy giải thuật (và ông ta bí) Bảo với [...]

Trong loạt 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 [...]