Người có thể xây dựng một phần mềm cho phép giải câu đố Queens nổi tiếng sẽ được trao giải 1 triệu đô la.
Các nhà nghiên cứu từ Đại học St.
Andrews gửi đi một thông điệp với nội dung bất kỳ lập trình viên nào có
thể viết một bộ code giúp giải quyết câu đố Queens nổi tiếng sẽ được
Viện Toán học Clay của Mỹ thưởng 1 triệu đô la. Thành quả này cũng sẽ có
ảnh hưởng rất lớn đến ngành công nghiệp công nghệ thông tin và toán
học. Iflscience đưa tin hôm 1/9.
Câu đố Queens là một câu đố rất đơn
giản. Nó yêu cầu bạn đặt tám quân hậu trên một bàn cờ vua theo một cách
làm sao để không có trường hợp hai quân hậu có thể tấn công lẫn nhau?
Đồng nghĩa, không có hai quân hậu có thể nằm trên cùng một hàng, cột
hoặc đường chéo. Nó được tạo ra lần đầu tiên vào năm 1850 và bất kỳ ai
với một chút kiên nhẫn cũng có thể giải quyết được.
Vấn đề là, máy tính không thể xử lý công
việc đó một cách dễ dàng. Máy tính sẽ so sánh tất cả các tùy chọn tiềm
năng và nhiều lựa chọn hơn bạn có, nó đòi hỏi rất nhiều máy tính để tìm
ra đáp án. Theo một bài viết trên Tạp chí Trí tuệ nhân tạo, sau khi bảng
cờ vua trở nên lớn hơn 1000 lần, các máy tính không thể giải được nữa.
“Nếu bạn có thể viết một chương trình
máy tính có thể giải quyết được vấn đề một cách nhanh chóng, bạn có thể
ứng dụng nó để giải quyết nhiều vấn đề quan trọng nhất đang ảnh hưởng
trực tiếp đến chúng ta hàng ngày”, Ian Gent, thành viên nhóm nghiên cứu
nói.
Điều này bao gồm những thách thức nhỏ
như làm thế nào để làm việc với một nhóm lớn bạn Facebook, những người
không quen biết nhau hoặc những người rất quan trọng, hay như chia nhỏ
các mã số để giữ cho tất cả các giao dịch trực tuyến được an toàn.
Đây chỉ là một biến thể của bài toán P
so với NP – một bài toán mở quan trọng trong lý thuyết khoa học máy
tính. Mô tả một cách đơn giản, bài toán đặt ra câu hỏi phải chăng bất kì
vấn đề nào có lời giải có thể được kiểm chứng “nhanh chóng” cũng có thể
được giải một cách “nhanh chóng”. Ví dụ, nếu câu hỏi là tìm các ước của
4,199 máy tính sẽ cần một chút thời gian để thử hàng loạt con số. Nhưng
thật nhanh chóng và dễ dàng để xác minh rằng 4,199 chỉ chia hết cho 13,
17 và 19 (ngoài 1 và chính nó).
Nhiều người tin rằng không phải mọi vấn
đề đều thỏa mãn luận điểm trên, nhưng nếu bạn nghĩ rằng bạn có thể viết
một thuật toán có thể làm được điều đó (hoặc chứng minh rằng nó không
thể), nó chắc chắn sẽ thu hút sự chú ý rất lớn từ các nhà nghiên cứu.
Đồng tác giả Dr Christopher Jefferson
cho biết: Giải thưởng trị giá 1.000.000 USD là rất lớn nhưng xứng đáng
cho bất cứ ai có thể xử lý được bài toán hóc búa nhưng nhiều giá trị
này.
Hoài Anh
bài toán khó đấy
Trả lờiXóa