Chung qui chỉ tại Cantor (2)
Ngô Quang Hưng | 10 tháng 02, 2005 | 
Bản để in
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 xếp là “tôi chịu thôi” (và mất việc)
- Ném vào sọt rác 6 tháng cuộc đời tìm giải thuật hiệu quả, và sau đó quay lại khả năng 2
- Tìm giải thuật cơ bắp (brute-force) tốn khoảng vài chục thế kỷ chạy mới xong (mất việc và mất mặt)
- Chứng minh cho xếp thấy là bài toán xếp cho không có giải thuật hiệu quả (cận dưới thời gian chạy là một hàm mũ chẳng hạn)
- Khả năng này rất khó xảy ra, kinh nghiệm cho thấy chứng minh những điều tương tự là cực kỳ khó. Với tất cả các bài toán loại này, cận dưới tốt nhất người ta biết là O(n), vô dụng.
- Chứng minh rằng bài toán xếp cho cũng khó như chục ngàn bài toán khác chưa ai biết giải.
A ha, khả năng số 6 nghe có vẻ được, nhưng cũng có vẻ lừa phỉnh vì ta thật ra không giải quyết vấn đề, mà bán cái nó cho nửa thế kỷ nghiên cứu của vô vàn người khác!
Nhưng làm thế nào ta chứng minh một điều như vậy? Thế nào gọi là khó? Thế nào là cái này khó tương đương cái kia? Về mặt trực quan thì có thể hiểu như sau: một bài toán khó là bài toán không giải được trong thời gian đa thức; hai bài toán khó tương đương nhau nếu giải bài này một cách hiệu quả thì cũng giải được bài kia một cách hiệu quả và ngược lại. Còn để trả lời nghiêm túc về mặt toán học, thì ta phải xem lại định nghĩa lại khái niệm giải thuật và các thứ liên quan.
Ta sẽ phải quay lại bánh xe lịch sử. Hành trình này đưa ta đến với Cantor, Russell, Hilbert, Gödel, Church, Turing, Cook/Levin, Karp và các ý tưởng tuyệt vời của họ.
A ha. Bài viết này cực kì thú vị. “Khó” có phải là một đại lượng không? Và nếu nó là một đại lượng thì nó có “cộng tính” không (f(x+y)=f(x)+f(y))? Liệu có thể xây dựng một độ đo cho cái sự “khó” không? Liệu có một cái không gian “khó” không?
Viết bởi Vương Đức Bình
A ha. Bài viết này cực kì thú vị. “Khó” có phải là một đại lượng không? Và nếu nó là một đại lượng thì nó có “cộng tính” không (f(x+y)=f(x)+f(y))? Liệu có thể xây dựng một độ đo cho cái sự “khó” không? Liệu có một cái không gian “khó” không?
Mo^ hi`nh cho ca’i su+. “kho’” ?
Viết bởi Vương Đức Bình
Trong ngữ cảnh của bài này thì sự “khó” không có cộng tính (additive). Nếu bạn đọc các bài tiếp trọng chuỗi bài thì sẽ thấy rằng “khó” ở đây mang nghĩa tập hợp hơn là một đại lượng, nghĩa là có bài khó và có bài không khó; có các bậc khó khác nhau (thời gian giải là O(n), O(n^2), O(n lg n), O(2^n), …); có bài cực kỳ khó (các bài không quyết định được); vân vân
Viết bởi Ngô Quang Hưng