Bài toán kinh điển của TG và phần thưởng triệu đô

[Romano]

Toán học là linh vực tính toán mà con người đã nghĩ ra từ lâu bên cánh đó là những bài toán đố để thử thach nhau. Một trong số đó là bài toán kinh điển mà cho tới nay vẫn chưa 1 ai có thể giải nổi. Đặc biệt phần thưởng của bài toan này vô cùng hấp dẫn lên tới 1 triệu đô la.200 năm trước, người ta chẳng có nhiều trò để chơi nên mới rảnh rỗi ngồi nghĩ ra những câu đố hóc búa nhằm “hack não” nhau. Những câu đố nổi tiếng ấy thường được đặt ra trên bàn cờ vua, và một trong số những bài toán nổi tiếng ấy là Câu đố Hoàn thiện n-Hậu – en-nờ số quân Hậu, chứ không phải là “nhậu”.
Nó khó đến mức các nhà nghiên cứu tại Đại học Thánh Andrews tin rằng trí tuệ nhân tạo phải mất tới vài ngàn năm để giải được nó, không phải trên một bàn cờ thường mà là trên một bàn có 1000x1000 ô. Đừng vội chỉ trích, máy tính tính toán nhanh lắm chứ, nên con số này hoàn toàn bình thường.
Mà bên cạnh đó, họ cũng treo giải 1 triệu USD cho bất kì ai có thể chứng minh rằng họ đúng hoặc sai.
Vấn đề toán học này lần đầu tiên được đưa ra vào năm 1949, thách thức người tham gia phải đặt được 8 con Hậu trên một bàn cờ 8x8 mà không có con Hậu nào có thể “ăn” được nhau - không được đặt 2 con hậu trên một hàng, một cột hay một đường chéo.
Có tất cả 4.426.165.368 cách đặt Hậu khác nhau, nhưng chỉ có 92 cách đặt thỏa mã điều kiện đề bài. Bạn có thể tham khảo câu đố này và cách giải tại đây.
Bằng cách thử lần lượt, máy tính có thể dễ dàng xử lý được vấn đề toán học này. Nhưng khi mà bàn cờ rộng hơn, số Hậu nhiều hơn thì vấn đề trở nên vô cùng phức tạp, thời lượng cần để giải tất nhiên sẽ dài hơn.
Ví dụ, nếu như đề bài là n-27 – giải bài trên bàn cờ 27x27, thì tổng số giải pháp khả thi sẽ là 2.34*10^17 – con số lên tới triệu tỉ.

Nghiên cứu mới đây được đăng tải trên Tạp chí Nghiên cứu Trí tuệ Nhân tạo chỉ ra rằng nếu như bài toán này có điều kiện là n-1.000 với 1.000 quân Hậu, thì AI sẽ không thể giải được, nó sẽ rơi vào trạng thái bất lực trước số lượng phép thử vô tận.
Bỗng nhiên, ta phát hiện ra lỗi của trí tuệ nhân tạo tưởng chừng như là tính toán giỏi giang lắm: chúng không thể sử dụng kết quả để tính ra một cách hiệu quả, mà cứ kéo dài vô tận.
Sau khi đăng tải nghiên cứu của mình, tiến sĩ Ian Gent, tiến sĩ Christopher Jefferson và tiến sĩ Peter Nightingale từ Đại học Thánh Andrews đã được Viện Toán học Clay liên hệ, đồng ý trao thưởng 1 triệu USD cho bất kì ai có thể dạy AI giải được bài toán đặt hậu với n-1.000 một cách nhanh chóng và chính xác.
Và nếu họ có thể dùng toán học chứng minh được AI không bao giờ giải được, họ cũng sẽ có thể cầm về 1 triệu USD.

Báo cáo cũng chỉ ra rằng nếu như hệ thống máy tính có thể hoàn thiện được câu đố bất khả thi này, nó sẽ có thể giải được những vấn đề cực kì phức tạp khác. Ví dụ đơn giản, nó có thể phá khóa được những lớp bảo mật cực kì phức tạp chẳng hạn.
Phóng viên Motherboard đã liên lạc với tiến sĩ Gent để hỏi rõ thực hư vấn đề, liệu rằng cái số tiền 1 triệu USD kia có thực không, hay cũng chỉ là một phần thưởng tượng trưng thôi, xét tới việc bài toán này quá khó.
“Hoàn toàn có thực”, ông Gent trả lời. “Tuy là phần thưởng không được trao luôn – bạn phải xuất bản thành công một báo cáo khoa học cùng với bằng chứng, lên trên một tạp chí uy tín và bạn cũng sẽ phải đợi 2 năm để xem có ai tìm ra lỗi của nghiên cứu đó không”.
Đối với những nhà nghiên cứu tại Đại học Thánh Andrews này, thì 2 năm chẳng nhằm nhò gì: họ tin rằng phải vài ngàn năm nữa mới có người tìm ra được giải pháp hiệu quả.
“Câu đố này không hẳn là một phép tính nhưng đa số người ta tin rằng không thể giải được nó một cách hiệu quả”, ông Gent giải thích.
“Nếu như điều đó là đúng, thì chẳng khó thể thấy cảnh những chương trình máy tính tân tiến nhất mất cả ngàn năm để giải được nó”. Việc lấy được giải thưởng 1 triệu USD kia dường như cũng bất khả thi, ai cũng tin vậy.