Mấy hôm nay tôi khá bận rộn tiếp khách của khoa (đi ăn, nói chuyện, xếp kế hoạch gặp gỡ, vân vân).
Đầu tiên là giáo sư Joe Mitchell của Stony Brook. Ông làm về hình học tính toán (computational geometry) và đã có các đóng góp đột phá trong ngành này. Kết quả nổi tiếng nhất của ông là một hệ xấp xỉ thời gian đa thức (polynomial time approximation scheme – PTAS) cho vấn đề người bán hàng trong không gian Euclid (Euclidean TSP). Kết quả này ra đời năm 1996, khi mà giáo sư Sanjeev Arora cũng xuất bản cùng kết quả. Bài nói của ông hôm qua giới thiệu rất nhiều các vấn đề về hình học tính toán chưa có lời giải.
Tôi giới thiệu cho Joe một vấn đề tôi đang làm: mô hình hóa hacking và tìm cách tốt nhất để hack vào một hệ thống trên mô hình này. Joe đặt góc nhìn hình học vào bài toán và thế là chúng tôi có bài toán mới khá thú vị:
- Giả sử bạn muốn đi từ A đến B nhanh nhất. Địa hình thì có đồi núi, sông, cầu, phà, bè, cầu khỉ, đường cao tốc … mà bạn phải vượt qua. Rải rác trong khu địa hình lộn xộn này có nhiều dụng cụ và các loại xe cộ (xe đạp, xe ô tô, thuyền bè, mái chèo, quần áo leo núi, vân vân). Mỗi loại có một tốc độ nhất định trong một địa hình nhất định. Làm thế nào mà bạn đi từ A đến B nhanh nhất?
[Chú ý: tôi đã chứng minh được là bài toán này không xấp xỉ được trong thời gian đa thức đến tỉ lệ xấp xỉ 2^{log^{1-d}(n)}, trong đó d tiến về 0 khi n tiến về vô cùng.]
Người kế tiếp là giáo sư Dave Farber, được mệnh danh là một trong những “ông đẻ” (grand farther) của Internet. Trong buổi ăn tối, Dave kể hết chuyện hài này đến giai thoại khác. Ông sẽ trình bày chiều nay.