Vào một buổi chiều tháng 7 năm 2024, Ryan Williams – nhà khoa học máy tính lý thuyết tại Viện Công nghệ Massachusetts (MIT) – đã bắt tay vào chứng minh chính mình sai. Hai tháng trước, ông phát hiện mối quan hệ đáng kinh ngạc giữa thời gian và bộ nhớ trong điện toán, nhưng kết quả này quá bất ngờ đến mức ông nghĩ phải có sai sót nào đó.
Mục lục
Bước Đột Phá Lịch Sử Sau 50 Năm
Sau hàng giờ kiểm tra kỹ lưỡng, Williams buộc phải thừa nhận: không có bất kỳ lỗi nào trong chứng minh của mình. Đây chính là bước tiến đầu tiên sau nửa thế kỷ giải quyết một trong những bài toán hóc búa nhất trong khoa học máy tính.
Khám Phá Làm Đảo Lộn Nhận Thức
Williams đã chứng minh rằng một lượng bộ nhớ nhỏ có thể mang lại hiệu quả tương đương với thời gian xử lý dài trong mọi phép tính toán. Khi công bố kết quả vào tháng 2/2024, giới nghiên cứu đã vô cùng kinh ngạc.
“Thật tuyệt vời. Thật đẹp đẽ,” Avi Wigderson từ Viện Nghiên cứu Cao cấp Princeton nhận xét.
Hiểu Về Tài Nguyên Tính Toán: Thời Gian vs Bộ Nhớ
Trong điện toán, thời gian và bộ nhớ (không gian) là hai tài nguyên cơ bản nhất. Cho đến nay, các thuật toán chỉ có thể hoạt động với lượng bộ nhớ tương đương thời gian chạy. Chứng minh của Williams đã phá vỡ giới hạn này.
Kết quả này không chỉ cho thấy chúng ta có thể tính toán với ít bộ nhớ hơn, mà còn hàm ý về những giới hạn không thể vượt qua của thuật toán trong một khoảng thời gian nhất định.
Con Đường Không Trải Hoa Hồng
Ryan Williams không phải là cái tên xa lạ với những đột phá trong lý thuyết độ phức tạp. Năm 2010, ông đã đạt được thành tựu quan trọng trên con đường giải quyết bài toán nổi tiếng về bản chất của các vấn đề khó.
Nhưng câu hỏi P so với PSPACE luôn ám ảnh ông từ thời đại học. “Nó luôn ở đâu đó trong tâm trí tôi,” Williams chia sẻ.
Sự Trở Lại Của “Pebble Mềm”
Bước ngoặt đến từ nghiên cứu của Stephen Cook và các cộng sự về bài toán đánh giá cây (tree evaluation problem). Năm 2023, James Cook (con trai Stephen) và Ian Mertz đã phát triển thuật toán giải quyết vấn đề này với ít bộ nhớ hơn nhiều so với dự đoán.
Williams nhận ra đây chính là chìa khóa: phương pháp “pebble mềm” (squishy pebbles) có thể áp dụng tổng quát để tiết kiệm bộ nhớ. Từ đó, ông tạo ra mô phỏng phổ quát mới, giảm đáng kể yêu cầu bộ nhớ so với thời gian chạy.
Ý Nghĩa Kép Của Khám Phá
Kết quả của Williams có hai mặt:
- Về mặt tích cực: thuật toán dùng ít bộ nhớ có thể giải quyết vấn đề đòi hỏi nhiều thời gian hơn
- Về mặt tiêu cực: một số bài toán không thể giải nếu không dùng nhiều thời gian hơn không gian
Tuy nhiên, khoảng cách giữa P và PSPACE vẫn còn rất lớn. Như Williams thừa nhận: “Tôi không bao giờ có thể chứng minh chính xác điều mình muốn, nhưng thứ tôi chứng minh được thường tốt hơn những gì tôi mong đợi.”
Khám phá này mở ra hướng đi mới cho nghiên cứu lý thuyết độ phức tạp, tiếp tục hành trình khám phá giới hạn của khả năng tính toán.
