Chung qui chỉ tại Cantor (2)

 

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:

1. Hỏi giáo sư dạy giải thuật (và ông ta bí)
2. Bảo với xếp là "tôi chịu thôi" (và mất việc)
3. 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
4. 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)
5. 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.
6. 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ọ