Trong hơn 40 năm, Avi Wigderson đã nghiên cứu các vấn đề. Nhưng với tư cách là một nhà lý thuyết về độ phức tạp tính toán, ông không nhất thiết phải quan tâm đến câu trả lời cho những vấn đề này. Anh ấy thường chỉ muốn biết liệu chúng có thể giải quyết được hay không và làm cách nào để nhận biết. “Tình huống thật nực cười,” nói Wigderson, một nhà khoa học máy tính tại Viện Nghiên cứu Cao cấp ở Princeton, New Jersey. Cho dù một câu hỏi có vẻ khó đến đâu, cách trả lời hiệu quả vẫn có thể nằm ngoài tầm với. “Theo những gì chúng tôi biết, đối với mọi vấn đề mà chúng tôi gặp phải và cố gắng giải quyết, chúng tôi không thể loại trừ rằng nó có một thuật toán có thể giải quyết được. Đây là vấn đề thú vị nhất đối với tôi.”

Hôm nay Wigderson được vinh danh là người chiến thắng trong cuộc thi Giải thưởng AM Turing, được coi là một trong những danh hiệu hàng đầu trong khoa học máy tính, vì những đóng góp nền tảng của ông cho lý thuyết tính toán. Công việc của Wigderson đã chạm tới gần như mọi lĩnh vực trên sân. Các đồng nghiệp, cộng tác viên và người được hướng dẫn của anh ấy nói rằng anh ấy luôn tìm thấy những cầu nối bất ngờ giữa các khu vực khác nhau. Và công trình của ông về tính ngẫu nhiên và tính toán, bắt đầu từ những năm 1990, đã tiết lộ mối liên hệ sâu sắc giữa toán học và khoa học máy tính làm nền tảng cho các cuộc nghiên cứu ngày nay.

Madhu Sudan, một nhà khoa học máy tính tại Đại học Harvard từng đoạt giải Rolf Nevanlinna năm 2002 (nay gọi là Giải Bàn tính), cho biết ảnh hưởng của Wigderson trong lĩnh vực này là không thể bỏ qua. Sudan cho biết: “Rất khó để làm việc trong bất kỳ lĩnh vực khoa học máy tính nào mà không thực sự giao thoa với công việc của Avi”. “Và ở mọi nơi, bạn đều tìm thấy những hiểu biết rất sâu sắc.” Ví dụ, vào cuối những năm 1980, Sudan đã làm việc với Wigderson trên một bài báo nghiên cứu mối liên hệ giữa một số hàm toán học và đa thức. Công việc đó đã khởi đầu toàn bộ sự nghiệp của Sudan. “Đây là điển hình của Avi,” Sudan nói. “Anh ấy bước vào một khoảng không gian nào đó, anh ấy hỏi những câu hỏi phù hợp và sau đó anh ấy tiếp tục.”

Wigderson lớn lên ở Haifa, Israel, là một trong ba người con trai của một y tá và một kỹ sư điện, cả hai đều sống sót sau Holocaust. Cha anh yêu thích các câu đố và đặc biệt quan tâm đến những ý tưởng cơ bản trong toán học mà ông đã chia sẻ với các con mình. Wigderson nói: “Anh ấy là người đã lây nhiễm loại virus này cho tôi. Khi bắt đầu học đại học vào những năm 1970 tại Technion ở Haifa, ông muốn học chuyên ngành toán, nhưng thay vào đó, cha mẹ lại hướng ông theo ngành khoa học máy tính. “Họ nghĩ có lẽ việc tôi có việc làm sau khi xong việc là một ý kiến ​​hay,” anh nói.

Ông đã tìm thấy một lĩnh vực giàu có với những câu hỏi sâu sắc, chưa có lời giải đáp mang tính chất toán học. Một trong những nỗ lực đột phá đầu tiên của ông tập trung vào một vấn đề có vẻ mâu thuẫn: liệu có thể thuyết phục người khác rằng một mệnh đề toán học đã được chứng minh mà không cần chỉ ra cách thức hay không.

“Người nhìn thấy bằng chứng không học được gì về chính bằng chứng đó,” nói Ran Raz, một nhà khoa học máy tính tại Đại học Princeton. Năm 1985, Shafi Goldwasser, Silvio Micali và Charles Rackoff đã giới thiệu khái niệm này về bằng chứng tương tác không có kiến ​​thức, chứng minh việc sử dụng nó cho một vài phát biểu. Wigderson, cùng với Micali và Oded Goldreich, sau đó đã giải thích ý tưởng đó, đặt ra các điều kiện cho thấy rằng nếu một tuyên bố có thể được chứng minh thì nó cũng có bằng chứng không có kiến ​​thức.

“Đây là kết quả quan trọng trong mật mã; nó cực kỳ trung tâm,” Raz nói. Bằng cách sử dụng bằng chứng không có kiến ​​thức, ai đó có thể chứng minh rằng họ đã mã hóa hoặc ký tin nhắn chính xác bằng khóa bí mật của mình mà không tiết lộ bất kỳ thông tin nào về nó. “Avi có một số kết quả cực kỳ quan trọng trong mật mã và đây có thể là kết quả quan trọng nhất trong số đó.”

Nhưng có lẽ kết quả cơ bản nhất của Wigderson nằm ở một lĩnh vực khác: liên kết độ cứng tính toán với ngẫu nhiên. Vào cuối những năm 1970, các nhà khoa học máy tính đã nhận ra rằng đối với nhiều vấn đề khó khăn, các thuật toán sử dụng tính ngẫu nhiên, còn được gọi là thuật toán xác suất, có thể vượt trội hơn rất nhiều so với các giải pháp xác định thay thế của chúng. trong một 1977 bằng chứng, ví dụ, Robert Solovay và Volker Strassen đã giới thiệu một thuật toán ngẫu nhiên có thể xác định liệu một số có phải là số nguyên tố nhanh hơn các thuật toán xác định tốt nhất vào thời điểm đó hay không.

Đối với một số bài toán, thuật toán xác suất có thể chỉ ra các bài toán xác định. Vào đầu những năm 1980, Wigderson đã làm việc với Richard Karp của Đại học California, Berkeley, để kết nối ý tưởng về tính ngẫu nhiên với các vấn đề được coi là khó về mặt tính toán, nghĩa là không có thuật toán xác định nào đã biết có thể giải quyết chúng trong một khoảng thời gian hợp lý. “Chúng tôi không biết làm thế nào để chứng minh rằng họ cứng rắn,” Wigderson nói. Tuy nhiên, anh ấy và Karp đã tìm ra một thuật toán ngẫu nhiên cho một vấn đề khó nhất định mà sau đó họ có thể loại bỏ ngẫu nhiên, phát hiện ra một thuật toán xác định cho nó một cách hiệu quả. Cùng lúc đó, các nhà nghiên cứu khác đã chỉ ra các giả định về độ cứng tính toán trong các vấn đề về mật mã có thể cho phép khử ngẫu nhiên nói chung như thế nào.

Tính hiệu quả phi lý của tính ngẫu nhiên khiến ông phải suy nghĩ về bản chất của tính ngẫu nhiên. Ông, giống như các nhà nghiên cứu khác vào thời điểm đó, đã đặt câu hỏi về tầm quan trọng của việc giải quyết vấn đề hiệu quả và trong những điều kiện nào thì nó có thể bị loại bỏ hoàn toàn. Ông nói: “Ban đầu, không rõ liệu đây có phải chỉ là sự ngu ngốc của chúng tôi hay không, hay chúng tôi không thể loại bỏ tính ngẫu nhiên”. “Nhưng câu hỏi lớn hơn là liệu tính ngẫu nhiên có luôn được loại bỏ một cách hiệu quả hay không.” Ông nhận ra rằng nhu cầu về tính ngẫu nhiên gắn liền với độ khó tính toán của bài toán.

Đối với một giấy 1994, ông và nhà khoa học máy tính Noam Nisan đã làm sáng tỏ mối liên hệ đó. Họ đã chứng minh rằng nếu tồn tại bất kỳ vấn đề khó khăn tự nhiên nào, như hầu hết các nhà khoa học máy tính nghi ngờ, thì mọi thuật toán ngẫu nhiên hiệu quả đều có thể được thay thế bằng một thuật toán xác định hiệu quả. “Bạn luôn có thể loại bỏ sự ngẫu nhiên,” Wigderson nói.

Điều quan trọng là họ phát hiện ra rằng các thuật toán xác định có thể sử dụng các chuỗi “giả ngẫu nhiên” - các chuỗi dữ liệu có vẻ ngẫu nhiên nhưng thực ra không phải vậy. Họ cũng chỉ ra cách sử dụng bất kỳ vấn đề khó khăn nào để xây dựng một trình tạo giả ngẫu nhiên. Việc đưa các bit giả ngẫu nhiên (thay vì các bit ngẫu nhiên) vào thuật toán xác suất sẽ mang lại một thuật toán xác định hiệu quả cho cùng một vấn đề.

Sudan cho biết bài báo đó đã giúp các nhà khoa học máy tính nhận ra mức độ ngẫu nhiên có thể giúp tiết lộ mức độ phức tạp của các vấn đề khó khăn và cách giải quyết chúng. “Đó không chỉ là sự ngẫu nhiên mà còn là nhận thức về sự ngẫu nhiên,” ông nói. “Đó là chìa khóa.”

Sudan chỉ ra rằng sự ngẫu nhiên dường như xuất hiện ở khắp mọi nơi nhưng trên thực tế lại cực kỳ khó tìm thấy. “Mọi người nói với bạn rằng các chữ số của số pi trông ngẫu nhiên, hoặc dãy số nguyên tố trông có vẻ ngẫu nhiên,” ông nói. “Chúng hoàn toàn được xác định rõ ràng, nhưng chúng có vẻ ngẫu nhiên đối với chúng tôi.” Ông nói, nhận thức về tính ngẫu nhiên nằm ở trung tâm của khoa học máy tính ngày nay. “Và đó là điều mà Avi đã quảng bá rất nhiều.”

Tính ngẫu nhiên đã trở thành một nguồn lực mạnh mẽ trong lý thuyết độ phức tạp, nhưng nó khó nắm bắt. Việc tung đồng xu và tung xúc xắc, Wigderson chỉ ra, không thực sự ngẫu nhiên: Nếu bạn có đủ thông tin về hệ thống vật lý thì kết quả hoàn toàn có thể dự đoán được. Ông nói, tính ngẫu nhiên hoàn hảo rất khó nắm bắt và khó xác minh.

Nhưng đối với Wigerson, các ví dụ về điện toán có ở khắp mọi nơi - không chỉ trong điện thoại thông minh, máy tính xách tay và các thuật toán mã hóa mà còn trong các hệ thống sinh học và vật lý. Trong những thập kỷ gần đây, những phát hiện từ lý thuyết tính toán đã mang lại những hiểu biết sâu sắc về một loạt vấn đề không mong đợi, từ việc bầy đàn chim tụ tập và kết quả bầu cử cho đến các phản ứng sinh hóa trong cơ thể. “Về cơ bản, bất kỳ quá trình tự nhiên nào cũng là một quá trình tiến hóa mà bạn có thể xem như sự tính toán, vì vậy bạn có thể nghiên cứu nó theo cách đó. Hầu hết mọi thứ đều được tính toán.”