Hãy tưởng tượng bạn đang tìm hiểu bản chất của tính toán. Bạn đang ở sâu trong vùng hoang dã, xa mọi con đường, và không thể hiểu được tin nhắn được khắc vào thân cây xung quanh bạn - BPP, AC⁰[m], Σ₂P, YACC và hàng trăm người khác. Các hình tượng đang cố nói với bạn điều gì đó, nhưng bắt đầu từ đâu? Bạn thậm chí không thể giữ chúng thẳng thắn.

Rất ít nhà nghiên cứu đã làm được nhiều như Russel Impagliazzo để vượt qua sự hỗn loạn dường như này. Trong 40 năm, Impagliazzo đã đi đầu trong lý thuyết độ phức tạp tính toán, nghiên cứu về độ khó nội tại của các vấn đề khác nhau. Câu hỏi mở nổi tiếng nhất trong lĩnh vực này, được gọi là bài toán P so với NP, hỏi liệu nhiều bài toán tính toán tưởng chừng khó có thực sự dễ hay không - với thuật toán phù hợp. Một câu trả lời sẽ có ý nghĩa sâu rộng đối với khoa học và tính bảo mật của mật mã hiện đại.

Trong những năm 1980 và 1990, Impagliazzo đóng vai trò lãnh đạo trong việc thống nhất cơ sở lý thuyết của mật mã. Năm 1995, ông trình bày rõ ràng tầm quan trọng của những phát triển mới này trong một bài báo mang tính biểu tượng, trình bày lại các giải pháp khả thi cho P so với NP và một số vấn đề liên quan bằng ngôn ngữ của năm thế giới giả định chúng ta có thể sinh sống, được đặt tên một cách kỳ lạ là Algorithmica, Heuristica, Pessiland, Minicrypt và Cryptomania. Năm thế giới của Impagliazzo đã truyền cảm hứng cho một thế hệ các nhà nghiên cứu và họ tiếp tục hướng dẫn nghiên cứu trong lĩnh vực con đang phát triển mạnh mẽ của siêu phức tạp.

Và đây không phải là thế giới duy nhất mà anh ấy mơ ước. Impagliazzo là người đam mê các trò chơi nhập vai trên máy tính bảng như Dungeons và Dragons, đồng thời ông rất thích phát minh ra các trò chơi này. bộ quy tắc mới và các cài đặt mới để khám phá. Tinh thần vui tươi tương tự đã làm sống động hơn 30 năm thực hành hài kịch ngẫu hứng của ông.

Impagliazzo cũng đã thực hiện công việc nền tảng làm sáng tỏ vai trò cơ bản của tính ngẫu nhiên trong tính toán. Vào cuối những năm 1970, các nhà khoa học máy tính phát hiện ra rằng tính ngẫu nhiên đôi khi có thể cải tiến thuật toán để giải quyết các vấn đề vốn đã xác định - một phát hiện phản trực giác khiến các nhà nghiên cứu bối rối trong nhiều năm. Công việc của Impagliazzo với nhà lý thuyết phức tạp Avi Wigderson và các nhà nghiên cứu khác vào những năm 1990 đã chỉ ra rằng nếu một số vấn đề tính toán nhất định về cơ bản thực sự khó, thì đó là luôn luôn có thể để chuyển đổi các thuật toán sử dụng tính ngẫu nhiên thành các thuật toán xác định. Và ngược lại, việc chứng minh tính ngẫu nhiên có thể bị loại bỏ khỏi bất kỳ thuật toán nào cũng sẽ chứng minh rằng những vấn đề thực sự khó khăn đang tồn tại.

Quanta đã nói chuyện với Impagliazzo về sự khác biệt giữa những bài toán khó và những câu đố khó, những lời tiên tri tư vấn và những bài học toán học của hài kịch ngẫu hứng. Cuộc phỏng vấn đã được cô đọng và chỉnh sửa cho rõ ràng.

Lần đầu tiên bạn quan tâm đến toán học là khi nào?

Tôi quan tâm đến toán thậm chí trước khi tôi thực sự biết nó là gì. Vào lớp ba, điểm môn toán của tôi bắt đầu tụt dốc vì chúng tôi phải ghi nhớ bảng cửu chương, và tôi đã từ chối. Mẹ tôi nói: “Nhưng Russell, con yêu toán, tại sao con không làm môn này?” Và tôi nói: “Đó không phải là toán, đó là khả năng ghi nhớ. Toán học thực sự không liên quan đến việc ghi nhớ.” Tất cả những gì tôi học được vào thời điểm đó là số học, vì vậy tôi không chắc mình lấy đâu ra khái niệm rằng toán học là những khái niệm trừu tượng.

Còn khoa học máy tính thì sao? Các phần của lĩnh vực này rất trừu tượng nhưng chúng không phải là điều mà hầu hết mọi người gặp phải lần đầu tiên.

Ở trường trung học, tôi đã học một khóa lập trình BASIC, nhưng thực sự rất khó để hoàn thành bất cứ việc gì. Các chương trình phải được chuyển sang băng giấy, phải chạy qua chiếc máy tính rất cũ này, chiếc máy tính này thường bị trục trặc và xé giấy của bạn làm đôi. Vì vậy, tôi nghĩ khoa học máy tính thật buồn tẻ.

Tôi dự định nghiên cứu logic. Nhưng rất nhiều khái niệm, khi bạn cố gắng hình thức hóa chúng, lại liên quan đến tính toán và đặc biệt là các giới hạn về tính toán. Những câu hỏi như “Làm sao chúng ta biết được những điều trong toán học là đúng?” và “Làm sao chúng ta hiểu được sự khó khăn khi làm toán?” dẫn đến khoa học máy tính lý thuyết và đặc biệt là lý thuyết phức tạp.

Một số công trình nổi tiếng nhất của bạn khám phá mối liên hệ giữa mật mã và lý thuyết độ phức tạp tính toán. Tại sao hai lĩnh vực đó có liên quan với nhau?

Khi thiết lập hệ thống mật mã, bạn cần phân biệt giữa người dùng hợp pháp — những người bạn muốn cấp quyền truy cập — và những người khác. Các bài toán khó tính toán cho chúng ta cách phân biệt các nhóm này dựa trên những gì họ biết. Nhưng nếu bạn muốn biết câu trả lời cho một vấn đề để phân biệt hai nhóm người, bạn không thể chỉ sử dụng bất kỳ bài toán khó nào - bạn cần một câu đố khó.

Sự khác biệt giữa một vấn đề và một câu đố là gì?

Nói chung, người đặt ra vấn đề có thể không biết câu trả lời. Câu đố là một vấn đề được thiết kế với câu trả lời trong đầu. Vậy tại sao chúng ta cần một câu đố? Bởi vì chúng ta cần có khả năng xác định liệu một người được cho là đã giải được nó có thực sự làm được hay không. Trong cuộc sống hàng ngày, chúng ta sử dụng các câu đố để giải trí nhưng chúng ta cũng sử dụng chúng trong lớp học để kiểm tra xem mọi người có hiểu bài hay không. Đây là điều xảy ra trong mật mã: Chúng ta sử dụng các câu đố để kiểm tra kiến ​​thức của ai đó.

Sự khác biệt giữa năm thế giới là cách họ trả lời câu hỏi “Có vấn đề gì khó không?” và “Có câu đố nào khó không?”

Những câu trả lời khác nhau đó diễn ra như thế nào?

Ở thế giới thứ nhất, Algorithmica, không có vấn đề gì khó cả. Bạn không cần phải biết ai đó đã giải quyết vấn đề của bạn như thế nào: Bạn luôn có thể giải quyết nó. Heuristica đang nói, "Chà, có lẽ một vài vấn đề khó khăn." Sau đó, chúng tôi đến Pessiland, nơi có nhiều vấn đề khó, nhưng hầu hết các câu đố thì không. Hầu như bất kỳ vấn đề nào tôi nghĩ ra khi tôi biết giải pháp thì bạn cũng sẽ có thể giải quyết được. Tất cả những thế giới này đều không tốt cho mật mã.

Trong Minicrypt, tôi có thể tạo các câu đố mà tôi biết cách giải nhưng vẫn thực sự là thử thách đối với bạn. Và cuối cùng, Cryptomania là một thế giới trong đó hai người có thể đứng ở một địa điểm công cộng nơi mà kẻ nghe trộm có thể nghe thấy và cùng nhau tạo ra một câu đố mà kẻ nghe trộm vẫn khó làm được.

Điều gì thúc đẩy bạn viết bài báo về năm thế giới?

Vào thời điểm đó, người ta biết rằng các câu trả lời khác nhau cho câu hỏi P và NP sẽ có tác động lớn đến loại vấn đề chúng ta có thể giải quyết cũng như loại bảo mật mà chúng ta có thể hy vọng, nhưng sự khác biệt về chất giữa các hình thức dễ dàng và khác nhau. độ cứng không thực sự rõ ràng.

Có một bài báo rất sâu sắc chỉ vài năm trước đó đã đưa ra sự khác biệt bằng cách sử dụng nhiều câu hỏi liên quan đến nhau với khoảng 20 câu trả lời khả thi. Một lý do khiến tôi muốn viết bài báo về năm thế giới là chúng tôi đã đạt được nhiều tiến bộ trong vài năm đó. Thật khó để tìm ra tên của 20 thế giới có thể tồn tại.

Vậy tại sao lại đóng khung nó theo cách đó, như những thế giới khác nhau với những cái tên kỳ quặc?

Tôi đã đồng ý viết bài báo này cho một hội nghị. Tôi đã thức khuya để cố gắng nghĩ xem mình sẽ nói gì, và đâu đó vào khoảng 1 giờ sáng, việc đóng khung các thế giới khác nhau có vẻ là một ý tưởng hay. Và sau đó tôi đọc nó vào sáng hôm sau và nó vẫn có vẻ là một ý tưởng ổn - đó là một cách để cho thấy những ý tưởng này sẽ thực sự ảnh hưởng đến thế giới như thế nào mà không bị cuốn vào các chi tiết định lượng. Điều khiến tôi hạnh phúc nhất về bài báo này là tôi nghe được từ những người đang nghiên cứu về sự phức tạp rằng đây là bài báo khiến họ quan tâm đến lĩnh vực này khi còn là sinh viên đại học.

Các nhà nghiên cứu đã loại trừ bất kỳ thế giới nào trong năm thế giới có thể tồn tại chưa?

Thực ra chúng tôi đang bổ sung thêm — mọi người đã bắt đầu nói về Obfustopia như một thế giới của các công cụ mã hóa thậm chí còn mạnh mẽ hơn. Hơi buồn một chút là chúng ta đã đạt được nhiều tiến bộ vào cuối những năm 1980 và chưa loại bỏ bất kỳ thế giới nào kể từ đó. Nhưng mặt khác, chúng ta biết nhiều hơn về mối liên hệ giữa các thế giới và có hình ảnh rõ ràng hơn nhiều về việc mỗi thế giới sẽ trông như thế nào.

Các thế giới giả thuyết cũng đóng một vai trò khác trong lý thuyết phức tạp, trong các bằng chứng giả định sự tồn tại của “các nhà tiên tri”. Vì vậy, trước hết, chính xác thì oracle là gì?

Hãy tưởng tượng ai đó chế tạo một thiết bị khéo léo có thể giải quyết một số vấn đề mà chúng ta không cần biết thuật toán để giải quyết vấn đề đó. Đó là ý nghĩa của một lời tiên tri. Nếu chúng ta có một thiết bị kỳ diệu như vậy và đặt nó vào trong máy tính của mình, nó có thể thay đổi ranh giới giữa những gì có thể tính toán được và những gì không thể tính toán được.

Các nhà nghiên cứu có nghĩ rằng những chiếc hộp ma thuật này thực sự có thể tồn tại?

Không, có lẽ chúng không tồn tại. Ban đầu, các kết quả oracle đã gây tranh cãi phần nào vì chúng quá mang tính giả thuyết. Nhưng có một cách mà họ có thể khai sáng là khi dùng lời tiên tri để mô hình hóa một tình huống lý tưởng. Giả sử bạn đang cố gắng chứng tỏ rằng A không nhất thiết ngụ ý B. Bạn bắt đầu với bối cảnh mà bạn có A cực đoan nhất và chứng tỏ rằng điều đó vẫn chưa đủ để đảm bảo B. Nếu bạn có thể chứng minh điều đó ngay cả khi tất cả các khả năng là có lợi cho bạn, bạn vẫn không thể chứng minh điều gì đó, đó là bằng chứng thực sự mạnh mẽ cho thấy sẽ rất khó để chứng minh.

Bạn cũng đã phát hiện ra mối liên hệ giữa độ cứng tính toán và tính ngẫu nhiên. Kết nối đó hoạt động như thế nào?

Đó thực sự là một cách nói rằng nếu bạn không hiểu điều gì đó thì nó có vẻ ngẫu nhiên. Giả sử tôi nói rằng tôi đang nghĩ về một con số từ một đến một nghìn. Nếu tôi chọn ngẫu nhiên một số, bạn có một phần nghìn cơ hội đoán được. Và nếu tôi hỏi - theo Monty Python - “Trong dặm một giờ, tốc độ bay trung bình của một con én châu Âu là bao nhiêu?” bạn có cơ hội tương tự Nó có thể đi hơn một dặm một giờ và có thể không vượt quá một nghìn dặm một giờ.

Đây thực sự không phải là ngẫu nhiên - đó là một câu hỏi có thể trả lời được. Chúng tôi chỉ có thể đo tất cả những con chim én bay xung quanh, nhưng thật khó để xác định với nguồn lực hạn chế, chẳng hạn như không có ngân sách để đo tốc độ chim én và không có nguồn cung cấp vô hạn cho những con én.

Vì vậy, hiểu biết sâu sắc là những bài toán khó mà giải pháp mà chúng ta không biết có thể cung cấp nguồn các số “giả ngẫu nhiên” trông có vẻ ngẫu nhiên.

Nhắc đến Monty Python, tôi biết bạn đã đóng phim hài ngẫu hứng được một thời gian dài - bạn bắt đầu như thế nào?

Tôi bắt đầu làm trợ lý giáo sư ở San Diego vào năm 1991. Và vào khoảng năm 94, tôi nghĩ, “Tôi thực sự không có nhiều cuộc sống ngoài khoa.” Thế là tôi nhận được tờ báo hàng tuần miễn phí và tôi xem qua danh sách các câu lạc bộ và hoạt động. Tôi đã loại bỏ tất cả mọi thứ ngoại trừ hài kịch ngẫu hứng - tôi nghĩ ít nhất cũng có lý khi tôi thấy ổn với việc đó. Tôi gặp vợ tôi trong lớp học dành cho người mới bắt đầu đó.

Cô ấy đã nghĩ gì vậy?

Cô ấy nói tôi thật sự rất tệ. Khi bạn là một nhà logic học, bạn được đào tạo để luôn suy nghĩ về sắc thái của từng từ. Bạn không muốn nói điều gì đó không đúng. Cải tiến tuyệt vời ở chỗ nó đảo ngược điều đó: Vấn đề không phải là nói điều gì đó hoàn hảo mà là bịa ra điều gì đó một cách nhanh chóng. Nó trái ngược với phần còn lại của cuộc đời tôi.

Người vợ hiện tại của tôi đã nghỉ học và một năm sau khi cô ấy quay lại lớp học, tôi đã gây được ấn tượng với cô ấy. Đó là 30 năm trước. Tôi vẫn học cùng lớp với cùng một người hướng dẫn.

Việc ứng biến có thay đổi cách bạn tiếp cận nghiên cứu của mình không?

Đó là một cách thực hành tốt để không quá chỉ trích mọi suy nghĩ của bạn. Điều đó đặc biệt hữu ích trong việc hợp tác. Khi làm việc với người khác, tôi thường nói những câu như “Nhưng ý tưởng đó sẽ không hiệu quả vì lý do sau. Điều đó không đúng theo nghĩa đen.” Trong ứng biến, bạn luôn phải chấp nhận những gì đối tác của bạn nói. Và tôi nghĩ đó là một thái độ tốt cần có, đặc biệt là khi bạn đang nghiên cứu với sinh viên: Đừng bác bỏ điều họ nói chỉ vì bạn biết nó sai. Có rất nhiều ý tưởng hay nhưng không đúng 100%.

Như thế nào?

Khi bạn đang cố gắng hiểu trực giác về một vấn đề, một điều hữu ích là hãy bắt đầu với một số giả định đơn giản hóa. Những giả định đó thường không đúng, nhưng chúng có thể giúp bạn đưa ra lộ trình. Hãy nói: “Nếu tôi có một con voi, tôi có thể vượt qua những ngọn núi. Tất nhiên là tôi không có voi. Nhưng nếu tôi làm vậy thì đây là cách tôi sẽ làm.” Và rồi bạn nhận ra, “Chà, có lẽ tôi không cần một con voi cho bước này. Một con la sẽ ổn thôi.”

Thế còn tình yêu của bạn với trò chơi nhập vai - điều đó có ảnh hưởng gì đến công việc của bạn không?

Nó có thể không ảnh hưởng đến tất cả nghiên cứu của tôi, nhưng chắc chắn nó đã ảnh hưởng đến bài báo về năm thế giới của tôi. Tôi luôn có mối quan tâm chung đến giả tưởng và khoa học viễn tưởng cũng như nghĩ ra những thế giới khả thi khác nhau - mọi thứ sẽ như thế nào nếu mọi thứ khác đi?

Tại sao trò chơi nhập vai lại là một cách hấp dẫn để khám phá thế giới giả định?

Những người say mê tiểu thuyết suy đoán luôn phát minh ra thế giới. Tolkien nổi tiếng nhất về điều đó và ông có trí tưởng tượng phong phú đến mức thế giới của ông thực sự có cảm giác như đang tồn tại. Đối với những người không có trí tưởng tượng như chúng tôi, cách tốt nhất để đạt được điều đó là mời mọi người vào bối cảnh của bạn và một trò chơi. là một cách để làm điều đó. Bây giờ nó không chỉ là thế giới của tôi. Nó có thể đã bắt đầu như tôi tưởng tượng, nhưng cũng giống như bất kỳ sự hợp tác nào, nhờ sự đóng góp của những người khác, nó đã phát triển vượt xa điều đó.