Lý thuyết tính toán đi về đâu?

 

Khoảng 10 năm trước, một nhóm các khoa học gia máy tính đầu ngành bao gồm cả các tên tuổi lớn như Richard Karp, Alfred Aho, David Johnson, và Christos Papadimitriou viết một báo cáo với tựa đề " Lý thuyết tính toán: mục tiêu và hướng đi" với dự định giới thiệu hướng nghiên cứu và mục tiêu cho toàn ngành. Trong thời gian đó (và đến nay), tiền dự án nghiên cứu cho nhóm lý thuyết tính toán không còn được nhiều như xưa, các sinh viên làm về lý thuyết tính toán tìm việc cũng khó hơn so với thời gian từ 1965 đến 1995. Báo cáo này đề nghị mọi người tìm cách hợp tác nhiều hơn với các nhánh khác của khoa học máy tính, các nhánh ứng dụng của khoa học máy tính (applied computer science), vân vân.

Có rất nhiều khoa học gia về lý thuyết tính toán không đồng ý với các điểm cơ bản trong báo cáo này, trong đó có giáo sư Goldreich (lúc đó đang ở MIT) và tiến sĩ Avi Wigderson (hiện ở khoa toán viện IAS [nơi Einstein làm khi xưa]). Goldreich và Wigderson viết một bài rất hay, bác cáo ở hội nghị STOC 1996 và đăng trong journal ACM Computing Surveys cùng năm, với tựa đề " Lý thuyết tính toán dưới góc nhìn khoa học".

Ai làm nghiên cứu về khoa học máy tính đều rất nên đọc hai báo cáo này và rút ra bài học cho riêng mình.

Ngoài hai báo cáo trên, có một workshop của NSF bảo trợ năm 1999 cũng ra một báo cáo trong tinh thần của đề tài này. Giáo sư Alan Selman của khoa tôi là một trong 14 người tham gia workshop này. Tham gia workshop còn có cả Richard Karp (!) và các tên tuổi lớn khác như Micheal Rabin (Harvard), Eva Tardos (Cornell), Richard Lipton (Princeton), v.v. Alan cho tôi biết các người tham dự workshop đã tránh các sai lầm trong báo cáo của Aho et al. lần đầu.

Tiến sĩ David Johnson của AT&T cũng đang viết một báo cáo với tựa đề " các thách thức cho khoa học máy tính lý thuyết".