Trong tuần đầu tiên của học kỳ mùa thu năm 2007, Marco Carmosino lê lết đến một lớp toán bắt buộc đối với tất cả các chuyên ngành khoa học máy tính tại Đại học Massachusetts, Amherst. Carmosino, sinh viên năm thứ hai, đang cân nhắc bỏ học đại học để thiết kế trò chơi điện tử. Sau đó, vị giáo sư đặt ra một câu hỏi đơn giản sẽ thay đổi cả cuộc đời ông: Làm thế nào để bạn biết toán học thực sự hoạt động?

“Điều đó khiến tôi ngồi dậy và chú ý,” nhớ lại Carmosino, hiện là nhà khoa học máy tính lý thuyết tại IBM. Anh ấy đã đăng ký tham gia một buổi hội thảo tùy chọn về công trình của Kurt Gödel, người mà những lập luận tự quy chiếu chóng mặt của ông lần đầu tiên phơi bày những giới hạn của lý luận toán học và tạo nền tảng cho tất cả những công việc sau này về những giới hạn cơ bản của tính toán. Đó là rất nhiều để đưa vào.

“Tôi 100% không hiểu,” Carmosino nói. “Nhưng tôi biết rằng tôi muốn.”

Ngày nay, ngay cả những nhà nghiên cứu dày dạn kinh nghiệm cũng thấy thiếu hiểu biết khi họ đối mặt với câu hỏi mở trọng tâm trong khoa học máy tính lý thuyết, được gọi là bài toán P so với NP. Về bản chất, câu hỏi đó đặt ra câu hỏi liệu nhiều vấn đề tính toán từ lâu được coi là cực kỳ khó có thể thực sự được giải quyết dễ dàng hay không (thông qua một lối tắt bí mật mà chúng tôi chưa khám phá ra), hoặc liệu chúng có thực sự khó như hầu hết các nhà nghiên cứu nghi ngờ hay không. Bị đe dọa không gì khác hơn là bản chất của những gì có thể biết được.

Bất chấp nhiều thập kỷ nỗ lực của các nhà nghiên cứu trong lĩnh vực lý thuyết phức tạp tính toán - nghiên cứu về những câu hỏi như vậy về độ khó nội tại của các vấn đề khác nhau - một giải pháp cho câu hỏi P so với NP vẫn khó nắm bắt. Và thậm chí còn không rõ ràng nên bắt đầu bằng chứng từ đâu.

“Không có bản đồ đường đi,” nói Michael Sipser, một nhà lý thuyết kỳ cựu về độ phức tạp tại Viện Công nghệ Massachusetts, người đã dành nhiều năm vật lộn với vấn đề này vào những năm 1980. "Giống như bạn đang đi vào vùng hoang dã."

Có vẻ như bản thân việc chứng minh rằng các bài toán tính toán khó giải quyết đã là một nhiệm vụ khó khăn. Nhưng tại sao nó quá khó? Và nó khó đến mức nào? Carmosino và các nhà nghiên cứu khác trong lĩnh vực con của siêu độ phức tạp đã định dạng lại các câu hỏi như thế này dưới dạng các bài toán tính toán, thúc đẩy lĩnh vực này tiến lên bằng cách lật ngược lại lăng kính của lý thuyết độ phức tạp.

“Bạn có thể nghĩ, 'OK, điều đó thật tuyệt. Có lẽ các nhà lý thuyết phức tạp đã phát điên,'” nói Rahul Ilango, một sinh viên tốt nghiệp tại MIT, người đã tạo ra một số kết quả thú vị nhất gần đây trong lĩnh vực này.

Bằng cách nghiên cứu những câu hỏi hướng nội này, các nhà nghiên cứu đã biết được rằng độ khó của việc chứng minh độ cứng tính toán gắn liền mật thiết với những câu hỏi cơ bản thoạt nghe có vẻ không liên quan. Làm thế nào khó để phát hiện các mẫu ẩn trong dữ liệu rõ ràng là ngẫu nhiên? Và nếu có những vấn đề thực sự khó khăn, thì chúng khó khăn đến mức nào?

“Rõ ràng là siêu phức tạp gần với trung tâm của mọi thứ,” nói Scott Aaronson, một nhà lý thuyết phức tạp tại Đại học Texas, Austin.

Đây là câu chuyện về con đường dài và quanh co đã dẫn các nhà nghiên cứu từ vấn đề P so với NP đến vấn đề siêu phức tạp. Đó không phải là một hành trình dễ dàng — con đường đầy những ngã rẽ và chướng ngại vật, và nó cứ lặp đi lặp lại. Tuy nhiên, đối với các nhà nghiên cứu siêu phức hợp, hành trình đến một cảnh quan chưa được khám phá là phần thưởng của chính nó. Bắt đầu hỏi những câu hỏi có vẻ đơn giản, cho biết Kabanet lễ tình nhân, một nhà lý thuyết phức hợp tại Đại học Simon Fraser ở Canada, và “bạn không biết mình sẽ đi đâu.”

ẩn số đã biết

Vấn đề P so với NP sở hữu cái tên mờ nhạt do thói quen sắp xếp các vấn đề tính toán thành các “rộng” của các nhà lý thuyết phức tạp.các lớp phức tạp” với các nhãn gợi ý về biểu tượng đánh dấu của Nasdaq. Một vấn đề tính toán là một vấn đề về nguyên tắc có thể được giải quyết bằng thuật toán - một danh sách hướng dẫn được chỉ định chính xác. Nhưng không phải tất cả các thuật toán đều hữu ích như nhau và sự thay đổi giữa các thuật toán gợi ý về sự khác biệt cơ bản giữa các vấn đề trong các lớp khác nhau. Thách thức đối với các nhà lý thuyết phức tạp là biến những gợi ý này thành các định lý chặt chẽ về mối quan hệ giữa các lớp phức tạp.

Những mối quan hệ này phản ánh những sự thật bất biến về tính toán vượt xa bất kỳ công nghệ cụ thể nào. Kabanets nói: “Điều này giống như việc khám phá ra các quy luật của vũ trụ.

“P” và “NP” là hai thành viên nổi tiếng nhất của một bầy thú đang phát triển của hàng trăm lớp phức tạp. Nói một cách đại khái, P là loại bài toán có thể giải dễ dàng, giống như sắp xếp theo thứ tự bảng chữ cái một danh sách. NP là loại bài toán có lời giải dễ kiểm tra, như câu đố sudoku. Vì tất cả các bài toán dễ giải cũng dễ kiểm tra, nên các bài toán trong P cũng thuộc NP. Nhưng một số bài toán NP có vẻ khó giải — bạn không thể trực giác ngay lập tức tìm ra lời giải cho câu đố sudoku mà không thử nhiều khả năng trước. Có thể nào độ cứng rõ ràng này chỉ là một ảo ảnh - rằng có một mẹo đơn giản duy nhất để giải quyết mọi vấn đề có thể kiểm tra dễ dàng?

Nếu vậy thì P = NP: Hai lớp là tương đương. Nếu đúng như vậy, phải có một số thuật toán khiến việc giải các câu đố sudoku khổng lồ trở nên đơn giản, tối ưu hóa các tuyến vận chuyển toàn cầu, phá vỡ mã hóa tiên tiến nhất và tự động hóa việc chứng minh các định lý toán học. Nếu P ≠ NP, thì nhiều vấn đề tính toán có thể giải được về nguyên tắc trong thực tế sẽ mãi mãi nằm ngoài tầm hiểu biết của chúng ta.

Các nhà nghiên cứu đã lo lắng về các giới hạn của suy luận toán học chính thức từ rất lâu trước khi bài toán P so với NP lần đầu tiên được trình bày rõ ràng - thực sự là từ rất lâu trước khi khoa học máy tính hiện đại ra đời. Năm 1921, vật lộn với cùng một câu hỏi sẽ thu hút sự chú ý của Carmosino gần một thế kỷ sau, nhà toán học David Hilbert đã đề xuất một chương trình nghiên cứu về nền tảng toán học trong sự chắc chắn tuyệt đối. Ông hy vọng bắt đầu từ một vài giả định đơn giản, được gọi là tiên đề, và rút ra một lý thuyết toán học thống nhất đáp ứng ba tiêu chí chính.

Điều kiện đầu tiên của Hilbert, tính nhất quán, là yêu cầu cơ bản để toán học không có mâu thuẫn: Nếu hai phát biểu trái ngược nhau có thể được chứng minh bắt đầu từ cùng một tiên đề, thì toàn bộ lý thuyết sẽ không thể cứu vãn được. Nhưng một lý thuyết có thể không có mâu thuẫn và vẫn bị hạn chế trong tầm với của nó. Đó là động lực cho điều kiện thứ hai của Hilbert, tính đầy đủ: yêu cầu rằng tất cả các mệnh đề toán học phải hoặc có thể chứng minh là đúng hoặc có thể chứng minh là sai. Tiêu chí thứ ba của ông, tính có thể quyết định, đòi hỏi một quy trình máy móc rõ ràng để xác định xem bất kỳ mệnh đề toán học nào là đúng hay sai. Phát biểu tại một hội nghị vào năm 1930, Hilbert tuyên bố: “Khẩu hiệu của chúng ta sẽ là 'Chúng ta phải biết, chúng ta sẽ biết.'”

Chỉ một năm sau, Gödel giáng đòn đầu tiên vào giấc mơ của Hilbert. Anh ta chứng minh rằng một tuyên bố tự đánh bại bản thân như “tuyên bố này không thể chứng minh được” có thể bắt nguồn từ bất kỳ tập hợp tiên đề thích hợp nào. Nếu một tuyên bố như vậy thực sự không thể chứng minh được, thì lý thuyết là không đầy đủ, nhưng nếu nó có thể chứng minh được, thì lý thuyết là không nhất quán - một kết quả thậm chí còn tồi tệ hơn. Trong cùng một bài báo, Gödel cũng chứng minh rằng không một lý thuyết toán học nào có thể chứng minh tính nhất quán của chính nó.

Các nhà nghiên cứu vẫn nuôi hy vọng rằng một lý thuyết toán học trong tương lai, mặc dù nhất thiết là chưa hoàn chỉnh, nhưng vẫn có thể được chứng minh là có thể quyết định được. Có lẽ họ có thể phát triển các quy trình xác định tất cả các tuyên bố có thể chứng minh được trong khi tránh xa các mệnh đề khó chịu như của Gödel. Rắc rối là không ai biết cách lập luận về những thủ tục giả định này.

Sau đó vào năm 1936, một sinh viên mới tốt nghiệp 23 tuổi tên là Alan Turing đã diễn đạt lại điều kiện có thể quyết định của Hilbert bằng ngôn ngữ tính toán lúc bấy giờ còn xa lạ và giáng cho nó một đòn chí mạng. Turing đã xây dựng một mô hình toán học - hiện được gọi là Máy turing — điều đó có thể đại diện cho tất cả các thuật toán khả thi và cho thấy rằng nếu quy trình của Hilbert tồn tại, thì nó sẽ phù hợp với mô hình này. Sau đó, ông sử dụng các phương pháp tự quy chiếu như của Gödel để chứng minh sự tồn tại của các câu lệnh không thể quyết định - hoặc tương đương, các vấn đề không thể tính toán được mà không thuật toán nào có thể giải quyết.

Chương trình của Hilbert nằm trong đống đổ nát: Sẽ mãi mãi có những giới hạn cơ bản về những gì có thể được chứng minh và những gì có thể tính toán được. Nhưng khi máy tính phát triển từ lý thuyết trừu tượng sang máy móc thực sự, các nhà nghiên cứu nhận ra rằng sự phân biệt đơn giản của Turing giữa các vấn đề có thể giải quyết được và không thể giải quyết được vẫn còn nhiều câu hỏi chưa được giải đáp.

Đến những năm 1960, các nhà khoa học máy tính đã phát triển các thuật toán nhanh để giải quyết một số vấn đề, trong khi đối với những người khác, các thuật toán duy nhất được biết đến lại cực kỳ chậm. Điều gì sẽ xảy ra nếu câu hỏi không chỉ là liệu các vấn đề có thể giải quyết được hay không, mà là chúng khó giải quyết đến mức nào?

Carmosino nói: “Một lý thuyết phong phú xuất hiện và chúng ta không biết câu trả lời nữa.

Đường dẫn phân kỳ

Để minh họa mức độ phức tạp của các câu hỏi về độ cứng, chúng ta hãy xem xét một cặp bài toán liên quan chặt chẽ liên quan đến đồ thị. Đây là mạng lưới các điểm, được gọi là các nút, được kết nối bằng các đường, được gọi là các cạnh. Các nhà khoa học máy tính sử dụng chúng để mô hình hóa mọi thứ từ tính toán lượng tử đến luồng giao thông.

Giả sử bạn được đưa cho một biểu đồ và được yêu cầu tìm một thứ gọi là đường đi Hamilton — một đường đi qua mỗi nút đúng một lần. Về nguyên tắc, vấn đề này rõ ràng là có thể giải quyết được: Chỉ có một số hữu hạn các đường đi khả dĩ, vì vậy nếu vẫn thất bại, bạn chỉ cần kiểm tra từng đường đi. Điều đó tốt nếu chỉ có một vài nút, nhưng đối với các biểu đồ lớn hơn một chút, số lượng khả năng vượt khỏi tầm kiểm soát, nhanh chóng khiến thuật toán đơn giản này trở nên vô dụng.

Có nhiều thuật toán đường dẫn Hamilton tinh vi hơn giúp tạo ra một cuộc chiến tốt hơn, nhưng thời gian mà các thuật toán yêu cầu để giải quyết vấn đề luôn tăng theo cấp số nhân với kích thước của biểu đồ. Đồ thị không nhất thiết phải quá lớn trước khi ngay cả những nhà nghiên cứu thuật toán tốt nhất đã phát hiện ra cũng không thể tìm thấy đường đi “trong bất kỳ khoảng thời gian hợp lý nào,” cho biết Russel Impagliazzo, một nhà lý thuyết phức tạp tại Đại học California, San Diego. “Và 'khoảng thời gian hợp lý', ý tôi là 'trước khi vũ trụ kết thúc'."

Bài toán đường đi Hamilton có một tính chất thú vị khác. Nếu ai đó tuyên bố đã tìm thấy đường đi Hamilton trên một đồ thị cụ thể, bạn có thể nhanh chóng kiểm tra xem lời giải có hợp lệ hay không, ngay cả khi đồ thị đó rất lớn. Tất cả những gì bạn cần làm là đi theo đường dẫn và đánh dấu vào từng nút một, kiểm tra để đảm bảo rằng bạn chưa đánh dấu vào bất kỳ nút nào hai lần. Nếu không có nút nào bị thiếu ở cuối, thì đường đi là Hamiltonian.

Thời gian cần thiết để chạy thuật toán kiểm tra giải pháp này tỷ lệ thuận với kích thước của biểu đồ. Điều đó đặt nó vào danh mục thuật toán đa thức rộng hơn, có thời gian chạy tăng lên khi các hàm đa thức có kích thước đồ thị. Tăng trưởng đa thức được chế ngự so với tăng trưởng theo cấp số nhân, vì vậy các thuật toán đa thức vẫn khả thi ngay cả trên các biểu đồ lớn. “Nó hiệu quả hơn rất nhiều,” Carmosino nói.

Bài toán đường đi Hamilton có một sự bất đối xứng hoàn toàn với nó: Bạn có thể xác minh nghiệm đúng bằng thuật toán đa thức nhanh, nhưng để tìm nghiệm bạn sẽ cần thuật toán hàm mũ chậm. Sự bất đối xứng đó có vẻ không có gì đáng ngạc nhiên — nhận ra một kiệt tác nghệ thuật dễ dàng hơn là tạo ra một kiệt tác, dễ kiểm tra một chứng minh toán học hơn là chứng minh một định lý mới — nhưng không phải tất cả các bài toán tính toán đều có đặc điểm bất đối xứng này. Trên thực tế, một bài toán rất giống với việc tìm đường đi Hamilton hoạt động hoàn toàn khác.

Giả sử bạn lại được cho một đồ thị, nhưng bây giờ bạn được yêu cầu tìm một “đường đi Euler” cắt mỗi cạnh đúng một lần. Một lần nữa, có một thuật toán đa thức để kiểm tra các giải pháp có thể, nhưng lần này cũng có một thuật toán đa thức để giải quyết vấn đề. Không có sự bất đối xứng ở đây. Trong lý thuyết phức tạp, một số đường dẫn có vẻ dễ tìm hơn những đường dẫn khác.

Cả bài toán đường đi Hamilton và bài toán đường đi Euler đều thuộc lớp phức tạp NP, được định nghĩa bao gồm tất cả các bài toán mà lời giải của chúng có thể được kiểm tra bằng thuật toán đa thức. Bài toán đường đi Euler cũng thuộc lớp P vì thuật toán đa thức có thể giải nó, nhưng nhìn chung, điều đó không đúng với bài toán đường đi Hamilton. Tại sao hai vấn đề đồ thị này, bề ngoài rất giống nhau, lại khác nhau một cách đáng kể như vậy? Đó là bản chất của vấn đề P so với NP.

Toàn cầu cứng

Lúc đầu, các lớp độ phức tạp có vẻ như là những phạm trù thuận tiện để sắp xếp các bài toán tương tự nhưng không liên quan trực tiếp — không ai nghi ngờ rằng việc tìm đường Hamilton có liên quan gì đến các bài toán tính toán khó khác.

Sau đó, vào năm 1971, trong vòng một năm sau khi chuyển đến Đại học Toronto sau khi bị từ chối nhiệm kỳ ở Hoa Kỳ, nhà lý thuyết phức hợp Stephen Cook xuất bản một kết quả phi thường. Anh ấy đã xác định một vấn đề NP cụ thể với một tính năng kỳ lạ: Nếu có một thuật toán đa thức có thể giải quyết vấn đề đó, thì nó cũng có thể giải quyết mọi vấn đề khác trong NP. Có vẻ như bài toán “phổ quát” của Cook là một cột duy nhất chống đỡ lớp các bài toán có vẻ khó, tách chúng ra khỏi các bài toán dễ dưới đây. Giải quyết được một vấn đề đó, và phần còn lại của NP sẽ sụp đổ.

Cook nghi ngờ rằng không có thuật toán nhanh nào cho bài toán phổ quát của mình, và ông nói giữa chừng bài báo, nói thêm, “Tôi cảm thấy rằng đáng để bỏ ra nhiều công sức cố gắng chứng minh phỏng đoán này.” “Nỗ lực đáng kể” hóa ra lại là một cách nói quá.

Cũng trong khoảng thời gian đó, một nghiên cứu sinh ở Liên Xô tên là Leonid Levin đã chứng minh một kết quả tương tự, ngoại trừ việc ông đã xác định được một số vấn đề phổ quát khác nhau. Ngoài ra, nhà lý thuyết phức hợp người Mỹ Richard Karp chứng minh rằng tính chất phổ quát được xác định bởi Cook (và Levin, mặc dù Karp và Cook không biết về công việc của Levin cho đến nhiều năm sau) bản thân nó gần như là phổ quát. Gần như mọi bài toán NP không có thuật toán đa thức đã biết — tức là gần như mọi bài toán dễ kiểm tra nhưng có vẻ khó — đều có cùng một thuộc tính, được gọi là tính đầy đủ của NP.

Điều này có nghĩa là tất cả các bài toán NP-đầy đủ - bài toán đường dẫn Hamilton, sudoku và hàng ngàn của những người khác - theo nghĩa chính xác là tương đương. Ilango nói: “Bạn có tất cả những nhiệm vụ tự nhiên khác nhau này, và tất cả chúng đều giống nhau một cách kỳ diệu. “Và chúng tôi vẫn không biết liệu nhiệm vụ tương tự đó có khả thi hay không.”

Giải quyết khó khăn của bất kỳ vấn đề NP-đầy đủ sẽ đủ để giải quyết câu hỏi P so với NP. Nếu P ≠ NP, sự khác biệt giữa các vấn đề dễ và khó được xác định bởi hàng nghìn cột mạnh như nhau. Nếu P = NP, cả tòa nhà đang chực chờ sụp đổ, chỉ chực chờ một mảnh rơi xuống.

Cook, Levin và Karp đã thống nhất những vấn đề tưởng như không liên quan đến nhau. Bây giờ tất cả những gì các nhà lý thuyết về độ phức tạp phải làm là giải quyết một vấn đề: Liệu P có = NP hay không?

Năm mươi năm sau, câu hỏi vẫn chưa được trả lời. Kabanets ví lý luận về các giới hạn của tính toán với việc khảo sát một lãnh thổ rộng lớn mà không có bất kỳ ý nghĩa nào về bức tranh toàn cảnh. Một sinh vật có sức mạnh tính toán không giới hạn có thể nhìn xuống từ đỉnh núi và bao quát toàn bộ cảnh quan cùng một lúc, nhưng những người bình thường không thể tin tưởng vào loại lợi thế đó. “Những người trong chúng ta ở dưới chân núi có thể cố gắng nhảy lên nhảy xuống để nhìn rõ hơn,” anh nói.

Giả sử rằng P = NP. Để chứng minh điều đó, các nhà nghiên cứu sẽ cần tìm một thuật toán nhanh cho một bài toán NP-đầy đủ, có thể ẩn trong một góc khuất nào đó của khung cảnh rộng lớn đó. Không có gì đảm bảo rằng họ sẽ sớm tìm ra nó: Các nhà lý thuyết về độ phức tạp thỉnh thoảng phát hiện các thuật toán khéo léo cho các vấn đề dường như khó (mặc dù không phải là NP-đầy đủ) chỉ sau nhiều thập kỷ làm việc.

Bây giờ giả sử rằng P ≠ NP. Chứng minh điều đó có vẻ còn khó hơn. Các nhà lý thuyết về độ phức tạp sẽ phải chứng minh rằng không có thuật toán nhanh nào có thể tồn tại, dự đoán hiệu quả và cản trở những nỗ lực tốt nhất của tất cả các nhà nghiên cứu trong tương lai.

Không biết bắt đầu từ đâu là một phần của vấn đề. Nhưng không phải là các nhà nghiên cứu chưa từng thử. Trong nhiều thập kỷ, họ đã tấn công vấn đề từ nhiều góc độ và tìm thấy con đường bị chặn ở mọi ngã rẽ. “Đó là một trong những sự thật trắng trợn nhất trong khoa học máy tính lý thuyết,” Carmosino nói. “Khi bạn có một hiện tượng lâu bền như vậy, bạn muốn có một lời giải thích nào đó.”

Vào năm cuối đại học của Carmosino, sự tò mò của anh ấy đã đưa anh ấy từ Gödel đến một khóa học sau đại học về lý thuyết phức tạp. Anh ấy ngạc nhiên khi nhận ra rằng mình đang dành nhiều thời gian cho bài tập về nhà hơn là cho dự án đam mê của mình, một chương trình máy tính có thể học cấu trúc tường thuật của truyện cổ tích và tạo ra những câu chuyện mới.

“Tôi nghĩ, 'Chà, mình cần phải xem xét điều này một cách nghiêm túc',” Carmosino nhớ lại. Chẳng bao lâu sau, anh ấy say mê môn học đến nỗi người cố vấn của anh ấy đã nhẹ nhàng đề nghị anh ấy xem xét lại các kế hoạch sau khi tốt nghiệp.

“Anh ấy nói, 'Bạn biết đấy, nếu bạn muốn tiếp tục làm điều này, nếu bạn muốn tiếp tục làm khoa học máy tính lý thuyết và lý thuyết phức tạp, bạn có thể: Nó được gọi là trường cao học',” Carmosino nói. Sau khi lấy bằng thạc sĩ, anh chuyển đến San Diego vào năm 2012 để học lấy bằng tiến sĩ do Impagliazzo hướng dẫn.

Ban đầu, mục tiêu chính của Carmosino là hiểu rõ hơn về một giấy mốc từ hai thập kỷ trước đó đã thu hút trí tưởng tượng của anh ấy. Bài báo đó, bởi các nhà lý thuyết phức tạp Alexander Razborov và Steven Rudich, đã chỉ ra rằng một chiến lược “tự nhiên” nhất định để chứng minh P ≠ NP gần như chắc chắn sẽ thất bại, bởi vì thành công sẽ phải trả giá đắt - sự phá vỡ hoàn toàn mật mã - mà các nhà nghiên cứu coi là rất khó xảy ra. Các nhà nghiên cứu giải thích kết quả của Razborov và Rudich là một rào cản đối với cách tiếp cận phổ biến này để chứng minh P ≠ NP.

“Rào cản bằng chứng tự nhiên” này chỉ là một trong nhiều rào cản đã biết để giải các bài toán mở trong lý thuyết độ phức tạp. Mỗi hành vi giống như một rào cản, cảnh báo rằng một con đường có vẻ hứa hẹn thực sự là một ngõ cụt. Cùng với nhau, những rào cản này chỉ ra rằng bất kỳ bằng chứng nào giải quyết vấn đề P so với NP sẽ phải khác hoàn toàn so với bất kỳ bằng chứng nào được sử dụng trong quá khứ; đó là lý do tại sao hầu hết các nhà nghiên cứu tin rằng một giải pháp vẫn còn xa vời. Nhưng ít nhất các rào cản cho họ biết nơi không nên tìm.

Ilango nói: “Lý thuyết phức tạp vừa bị nguyền rủa vừa được ban phước với rất nhiều rào cản.

Vào thời điểm Carmosino gặp phải rào cản bằng chứng tự nhiên, nó đã gần 20 tuổi. Nhưng ông ngờ rằng nó có nhiều bài học hơn cho các nhà nghiên cứu. Cảm giác đó một ngày nào đó sẽ được chứng minh khi anh ấy và ba đồng nghiệp chứng minh một kết quả đáng ngạc nhiên bằng cách kiểm tra rào cản bằng chứng tự nhiên từ góc độ siêu phức tạp. Bằng chứng của họ là một trong số ít kết quả quan trọng khơi dậy mối quan tâm mới về siêu phức hợp, dẫn đến một loạt tiến bộ trong vài năm qua.

Nhưng để lần theo dấu vết từ rào cản bằng chứng tự nhiên đến siêu phức tạp, chúng ta sẽ phải quay trở lại nơi chúng ta đã rời bỏ các nhà nghiên cứu vào những năm 1970, khi họ lần đầu tiên bắt đầu giải quyết vấn đề P so với NP. Điều gì đã khiến việc chứng minh các vấn đề trở nên khó khăn đến vậy?

Một con đường quanh co

Lúc đầu, các nhà nghiên cứu đã cố gắng chứng minh P ≠ NP — nghĩa là chứng minh rằng một số bài toán NP không thể giải được bằng bất kỳ thuật toán đa thức nào — bằng cách sử dụng các biến thể của các kỹ thuật mà Turing đã sử dụng để chứng minh rằng một số bài toán không thể giải được bằng bất kỳ thuật toán nào. . Nhưng họ nhanh chóng phát hiện một bằng chứng cho thấy những phương pháp đó sẽ không hoạt động - rào cản lớn đầu tiên để giải quyết câu hỏi P so với NP. Vì vậy, họ bắt đầu tìm kiếm một cách tiếp cận khác, và họ nhanh chóng tìm thấy một cách tiếp cận trong tác phẩm đương đại của Turing. claude shannon.

Shannon, người lớn lên ở một thị trấn nhỏ phía bắc Michigan, dường như là một nhân vật không thể mở ra thời đại thông tin. Tuy nhiên, ông đã minh họa bản chất liên ngành của ngành khoa học máy tính mới nổi, cảm thấy như ở nhà trong kỹ thuật điện và logic toán học. trong anh ấy luận án thạc sĩ, Shannon đã chỉ ra cách các mạch làm bằng công tắc điện cơ có thể biểu diễn các biểu thức logic liên quan đến các biến Boolean — các đại lượng chỉ có thể nhận hai giá trị (chẳng hạn như đúng hoặc sai, hoặc 1 và 0).

Trong các biểu thức này, các biến Boolean được liên kết với nhau bằng các “cổng logic” AND, OR và NOT. Ví dụ, biểu thức cơ bản A AND B là đúng khi cả A và B đều đúng và sai nếu ngược lại; Mặt khác, A OR B là đúng nếu ít nhất một trong hai biến là đúng. Một cổng NOT thậm chí còn đơn giản hơn: Nó đảo ngược giá trị của một biến duy nhất. Với đủ các khối xây dựng cơ bản này, bạn có thể thực hiện bất kỳ tính toán nào.

“Khi bạn nhìn vào máy tính của mình, vào cuối ngày, nó đang làm gì? Nó đang chạy một mạch,” Ilango nói.

Công trình của Shannon đã đề xuất một cách mới để các nhà lý thuyết suy nghĩ về độ khó của các bài toán tính toán, được gọi là “độ phức tạp của mạch”, mặc dù các mạch được đề cập chỉ là những khái niệm toán học trừu tượng. Trong một thời gian, các nhà nghiên cứu nghĩ rằng phương pháp này có thể là cách để giải quyết P so với NP, nhưng cuối cùng con đường dẫn đến rào cản bằng chứng tự nhiên.

Khung độ phức tạp của mạch yêu cầu xem xét lại các khái niệm cơ bản nhất trong mô hình tính toán của Turing. Ở đây, thay vì các vấn đề tính toán và các thuật toán giải quyết chúng, các nhà nghiên cứu xem xét các hàm Boolean và các mạch tính toán chúng. Một hàm Boolean nhận các biến Boolean — true và false, 1 và 0 — và xuất ra giá trị đúng hoặc sai, 1 hoặc 0. Và giống như một thuật toán, một mạch mô tả quy trình tạo đầu ra cho bất kỳ đầu vào nào.

“Tôi hiểu rằng mọi người bắt đầu làm việc với độ phức tạp của mạch vì họ cho rằng máy Turing quá phức tạp,” nói Ryan William, một nhà lý thuyết phức tạp tại MIT. “Chúng ta có thể nghiên cứu từng cổng một.”

Giống như có thể có nhiều thuật toán để giải quyết bất kỳ vấn đề tính toán cụ thể nào, một số thuật toán nhanh hơn các thuật toán khác, nhiều mạch khác nhau có thể tính toán bất kỳ hàm Boolean cụ thể nào, một số có ít cổng hơn các thuật toán khác. Các nhà nghiên cứu định nghĩa độ phức tạp mạch của một hàm là tổng số cổng trong mạch nhỏ nhất tính toán hàm đó. Đối với một chức năng có số lượng biến đầu vào cố định, độ phức tạp của mạch cũng là một số cố định — đối với một số chức năng cao hơn so với các chức năng khác.

Nhưng trong nhiều trường hợp, bạn có thể xét các phiên bản phức tạp hơn của cùng một hàm bằng cách tăng số lượng biến đầu vào, giống như bạn có thể làm cho bài toán đường Hamilton trở nên khó hơn bằng cách xét các đồ thị lớn hơn. Sau đó, các nhà nghiên cứu xem xét câu hỏi tương tự mà họ đặt ra khi nghiên cứu thời gian chạy thuật toán: Số lượng cổng tối thiểu cần thiết để tính toán hàm Boolean có tăng theo cấp số nhân hoặc đa thức khi số lượng biến đầu vào tăng lên không? Các nhà nghiên cứu gọi hai loại chức năng này là “dễ tính toán” và “khó tính toán”.

Một hàm Boolean dễ tính toán tương tự như một bài toán tính toán trong lớp P — một bài toán có thể được giải bằng một thuật toán chạy trong thời gian đa thức. Nhưng cũng có những chức năng tương tự như các bài toán NP khó, trong đó cách tốt nhất mà các nhà nghiên cứu đã phát hiện ra để tính toán các phiên bản lớn hơn dần dần đòi hỏi số lượng cổng tăng theo cấp số nhân, tuy nhiên câu trả lời có thể dễ dàng kiểm tra. Nếu các nhà lý thuyết về độ phức tạp có thể chứng minh rằng thực sự không có cách nào tốt hơn để tính một hàm như vậy, thì điều đó có nghĩa là P ≠ NP.

Đây là chiến lược mà hầu hết các nhà lý thuyết phức tạp theo đuổi trong những năm 1980. Và tỷ lệ cược đã đứng về phía họ. Shannon đã có chứng minh vào năm 1949 rằng hầu hết mọi bảng chân lý Boolean (chỉ là một danh sách dài tất cả các đầu vào và đầu ra có thể có của hàm Boolean có kích thước cố định) đều có độ phức tạp của mạch thực tế càng cao càng tốt. Ông đã sử dụng một lập luận đơn giản đến kinh ngạc: Có ít cách để kết hợp một số ít cổng hơn là có nhiều cách để kết hợp nhiều cổng.

Aaronson nói: “Không có đủ mạch điện nhỏ để đi vòng quanh.

Vì vậy, các nhà lý thuyết phức tạp thấy mình trong một tình huống kỳ lạ. Nếu gần như mọi bảng chân lý đều có độ phức tạp mạch cao, thì gần như mọi hàm Boolean đều khó tính toán. Các nhà nghiên cứu chỉ cần xác định một chức năng duy nhất như vậy cũng được biết là thuộc lớp NP. Nó khó đến mức nào?

anh em tiền điện tử

Lúc đầu, tiến độ rất nhanh. Năm 1981, Sipser và hai cộng sự chứng minh rằng một hàm Boolean nhất định chắc chắn khó tính toán nếu họ sử dụng các mạch có những hạn chế nhất định về cách sắp xếp các cổng.

“Điều tưởng tượng là bạn sẽ có thể chứng minh những điều về các mô hình bị hạn chế này, và sau đó dựa trên những gì bạn đã học được để làm việc với ngày càng ít hạn chế hơn,” Sipser nói.

Năm 1985, Razborov thực hiện một bước tiến lớn tiếp theo. Anh ấy mới bắt đầu học cao học ở Moscow và vô tình tham gia nỗ lực này khi đang giải một bài toán thuộc một nhánh toán học khác, nơi hóa ra việc giải bài toán P so với NP là điều kiện tiên quyết.

Razborov nói: “Tôi chỉ đơn giản là may mắn vì tôi không biết vấn đề này khó đến mức nào. “Nếu không thì có lẽ tôi đã không bắt đầu.”

Razborov đã phân tích các mạch chỉ chứa cổng AND và OR, và chứng minh rằng một chức năng cụ thể khó tính toán bằng cách sử dụng các mạch như vậy, bất kể cổng được sắp xếp như thế nào - hơn nữa, chức năng đó được biết là NP-đầy đủ. Tất cả những gì các nhà nghiên cứu phải làm để giải quyết P so với NP là mở rộng các kỹ thuật của Razborov sang các mạch có cổng KHÔNG.

Razborov nói: “Có một loại cảm giác chung rằng chỉ cần tiến thêm một bước nữa, tấn công thêm một lần nữa và chúng ta sẽ đạt được mục tiêu. Nhưng đó không phải là những gì đã xảy ra. Bản thân Razborov đã chứng minh rằng phương pháp của ông sẽ thất bại nếu KHÔNG thêm các cổng vào hỗn hợp và không ai có thể tìm ra cách khác để tiến lên. Nhiều năm trôi qua, anh bắt đầu tự hỏi tại sao dấu vết lại biến mất.

Tại Hoa Kỳ, Rudich cũng đang cân nhắc câu hỏi tương tự. Anh ấy và Impagliazzo là bạn học đại học đã cùng nhau học cao học. Tình bạn của họ bắt nguồn từ niềm đam mê chung với các chứng minh tự quy chiếu của Gödel và Turing và ý nghĩa của chúng đối với nền tảng của toán học và khoa học máy tính.

“Trò đùa của chúng tôi là chúng tôi sẽ nhận được một nút có nội dung 'tự tham khảo',” Impagliazzo nói.

Khi còn là sinh viên cao học, cả Rudich và Impagliazzo đều nghiên cứu về cơ sở lý thuyết phức tạp của mật mã học, một chủ đề có lẽ mang lại động lực thực tiễn tốt nhất để cố gắng chứng minh P ≠ NP. Các nhà mật mã che giấu các thông điệp bí mật bằng cách che giấu chúng trong “tính ngẫu nhiên giả” — một thông điệp được mã hóa theo cách này sẽ trông giống như một dãy số ngẫu nhiên đối với bất kỳ kẻ nghe lén nào, nhưng nó vẫn có thể được giải mã bởi người nhận dự kiến. Nhưng làm thế nào bạn có thể chắc chắn rằng một kẻ nghe lén sẽ thấy quá khó để phá mã?

Đó là lúc lý thuyết về độ phức tạp xuất hiện. Các phương pháp mã hóa được sử dụng rộng rãi nhất hiện nay đều dựa trên các bài toán NP có vẻ khó — để giải mã tin nhắn, kẻ tấn công sẽ cần một thuật toán nhanh chưa được khám phá để giải quyết vấn đề. Để chứng minh rằng các phương pháp này thực sự an toàn, một điều bạn cần làm là chứng minh rằng P ≠ NP. Nếu không có bằng chứng, Sipser nói, tất cả những gì bạn có thể làm là “hy vọng rằng bất cứ ai mà bạn đang cố giữ bí mật không phải là một nhà toán học giỏi hơn bạn.”

Mặc dù hấp dẫn theo đúng nghĩa của nó, mật mã học dường như khác xa với những lập luận tự quy chiếu đã lần đầu tiên lôi kéo Rudich và Impagliazzo vào lĩnh vực này. Nhưng khi Rudich đấu tranh để hiểu tại sao cách tiếp cận độ phức tạp của mạch điện lại bị đình trệ, ông bắt đầu nhận ra rằng xét cho cùng thì hai đối tượng cũng không quá xa nhau. Các nhà nghiên cứu chiến lược đã áp dụng trong nỗ lực chứng minh P ≠ NP có đặc tính tự chuốc lấy thất bại gợi nhớ đến mệnh đề nổi tiếng của Gödel “tuyên bố này không thể chứng minh được” — và mật mã học có thể giúp giải thích tại sao. Ở Nga, Razborov cũng phát hiện ra mối liên hệ tương tự vào khoảng thời gian đó. Đây là những hạt giống của hàng rào bằng chứng tự nhiên.

Điểm căng thẳng cốt lõi của rào cản chứng minh tự nhiên là nhiệm vụ phân biệt các hàm có độ phức tạp cao với các hàm có độ phức tạp thấp cũng tương tự như nhiệm vụ phân biệt tính ngẫu nhiên thực sự với tính giả ngẫu nhiên được sử dụng để mã hóa thông điệp. Chúng tôi muốn chỉ ra rằng các hàm có độ phức tạp cao hoàn toàn khác với các hàm có độ phức tạp thấp, để chứng minh P ≠ NP. Nhưng chúng tôi cũng muốn tính giả ngẫu nhiên không thể phân biệt được với tính ngẫu nhiên, để tin tưởng vào tính bảo mật của mật mã. Có lẽ chúng ta không thể có nó theo cả hai cách.

Một trò đùa độc ác

Năm 1994, Razborov và Rudich nhận ra rằng họ đã đạt được những hiểu biết tương tự, và họ bắt đầu làm việc cùng nhau để kết hợp các kết quả của mình. Đầu tiên, họ quan sát thấy rằng tất cả những nỗ lực trước đây để chứng minh P ≠ NP sử dụng độ phức tạp của mạch đã áp dụng cùng một chiến lược chung: Xác định một thuộc tính đặc biệt của hàm Boolean NP-đầy đủ, sau đó chứng minh rằng không có hàm dễ tính toán nào có thể chia sẻ thuộc tính đó. Điều đó cho thấy rằng hàm NP-đầy đủ đã chọn thực sự khó tính toán, chứng tỏ P ≠ NP.

Sipser, Razborov và những người khác đã sử dụng thành công chiến lược tương tự này để chứng minh các kết quả hạn chế hơn của họ và trong mọi trường hợp, thuộc tính đặc biệt mà các nhà nghiên cứu đã xác định được chia sẻ bởi hầu hết các hàm Boolean. Razborov và Rudich đã đặt ra thuật ngữ “bằng chứng tự nhiên” để chỉ trường hợp này khi tài sản được chia sẻ rộng rãi, đơn giản vì không có giải pháp thay thế nào được biết đến. Nếu có thể có bằng chứng “không tự nhiên”, thì chúng phải rất phản trực giác và xứng đáng với cái tên đó.

Razborov và Rudich sau đó đã chứng minh kết quả chính của họ: Một bằng chứng tự nhiên của P ≠ NP sẽ đòi hỏi một sự hiểu biết rất toàn diện về sự khác nhau của các hàm dễ tính toán và khó tính toán, và kiến ​​thức đó cũng có thể thúc đẩy một thuật toán nhanh để phát hiện dễ dàng -to-compute chức năng ngay cả khi chúng phức tạp bề ngoài. Nếu các nhà lý thuyết về độ phức tạp đã thành công trong việc chứng minh P ≠ NP một cách tự nhiên, thì họ đã phát hiện ra một cách gần như không thể sai lầm để lướt qua một bảng chân lý tùy ý và xác định xem hàm tương ứng có độ phức tạp mạch cao hay thấp - một kết quả mạnh mẽ và tổng quát hơn nhiều so với họ đã đặt ra để chứng minh.

Carmosino nói: “Bạn gần như không thể không nhận được nhiều hơn những gì bạn đã mặc cả.

Nó giống như thể bạn cố gắng kiểm tra tính xác thực của một tuyên bố cụ thể, nhưng mọi nỗ lực đều trở thành bản thiết kế cho máy phát hiện nói dối đa năng — điều đó có vẻ quá tốt để trở thành sự thật. Đối với các nhà lý thuyết phức tạp, sức mạnh đáng kinh ngạc của các bằng chứng tự nhiên cũng làm cho khả năng thành công dường như ít hơn. Nhưng nếu một bằng chứng như vậy thành công, thì những hậu quả không mong đợi sẽ là một tin xấu đối với mật mã học, bởi vì mối liên hệ giữa độ phức tạp của mạch và tính giả ngẫu nhiên.

Để hiểu mối liên hệ này, hãy tưởng tượng nhìn vào cột đầu ra trong bảng chân lý của hàm Boolean với nhiều biến đầu vào và thay thế mọi “true” bằng 1 và mọi “false” bằng 0:

Nếu hàm Boolean có độ phức tạp mạch cao, thì về nguyên tắc, danh sách dài các đầu ra đó sẽ không thể phân biệt được với một chuỗi thực sự ngẫu nhiên gồm các số 0 và 1 — chẳng hạn như một chuỗi thu được bằng cách tung đồng xu nhiều lần. Nhưng nếu chức năng có độ phức tạp mạch thấp, thì chuỗi phải có mô tả đơn giản, ngắn gọn ngay cả khi nó có vẻ phức tạp. Điều đó làm cho nó rất giống với các chuỗi giả ngẫu nhiên được sử dụng trong mật mã, mà mô tả ngắn gọn của nó chính là thông điệp bí mật được chôn giấu trong tính ngẫu nhiên rõ ràng đó.

Vì vậy, kết quả của Razborov và Rudich cho thấy rằng bất kỳ bằng chứng tự nhiên nào về P ≠ NP cũng sẽ tạo ra một thuật toán nhanh có thể phân biệt các chuỗi giả ngẫu nhiên chứa các thông điệp ẩn với các chuỗi thực sự ngẫu nhiên. Mật mã an toàn sẽ là không thể - hoàn toàn ngược lại với những gì các nhà nghiên cứu hy vọng thiết lập bằng cách chứng minh P ≠ NP.

Mặt khác, nếu có thể sử dụng mật mã an toàn, thì bằng chứng tự nhiên không phải là chiến lược khả thi để chứng minh P ≠ NP — điều kiện tiên quyết cho mật mã an toàn. Tóm lại, đó là rào cản bằng chứng tự nhiên. Có vẻ như những người theo thuyết phức tạp đang phải hứng chịu một trò đùa độc ác.

“Nếu bạn tin vào độ cứng, thì bạn nên tin rằng rất khó để chứng minh độ cứng,” Kabanets nói.

Vào Metaverse

Mối liên hệ giữa hàm ý của phỏng đoán P ≠ NP và khó khăn trong việc chứng minh nó thật hấp dẫn, nhưng lại khó xác định. Đối với một điều, rào cản bằng chứng tự nhiên chỉ chặn một cách tiếp cận để chứng minh P ≠ NP. Mặt khác, nó liên kết khó khăn trong việc chứng minh P ≠ NP không phải với bản thân P ≠ NP, mà với sự tồn tại của mật mã an toàn — một vấn đề liên quan chặt chẽ nhưng không hoàn toàn tương đương. Để thực sự hiểu được mối liên hệ này, các nhà nghiên cứu sẽ phải làm quen với siêu độ phức tạp.

“Có một trực giác rằng 'ồ, bởi vì P ≠ NP, rất khó để chứng minh rằng P ≠ NP',” Williams nói. “Nhưng để hiểu được trực giác này, bạn phải bắt đầu nghĩ về nhiệm vụ chứng minh một thứ như P ≠ NP như một bài toán tính toán.”

Đó là những gì Kabanets đã làm khi còn là một sinh viên tốt nghiệp. Anh ấy lớn lên ở Ukraine, và anh ấy đã hoàn thành chương trình đại học về khoa học máy tính hai năm sau khi Liên Xô sụp đổ. Trong tình trạng hỗn loạn sau đó, ông có rất ít cơ hội để theo đuổi các chủ đề lý thuyết mà ông quan tâm nhất.

Kabanets nhớ lại: “Tôi muốn làm điều gì đó hàn lâm hơn. “Và tôi cũng tò mò muốn nhìn thế giới.” Anh ấy chuyển đến Canada để học cao học, và đó là nơi anh ấy biết về rào cản bằng chứng tự nhiên. Giống như Carmosino, Kabanets hài lòng với kết quả này. Anh ấy nói: “Có vẻ như rất sâu sắc rằng bạn có mối liên hệ này.

Vào năm 2000, vào cuối thời gian học cao học, anh ấy nhận thấy rằng rào cản bằng chứng tự nhiên liên tục xuất hiện trong các cuộc trò chuyện của anh ấy với Jin Yi Cai, một nhà lý thuyết về sự phức hợp đang đến thăm Toronto vào thời điểm nghỉ phép. Họ bắt đầu coi rào cản không phải là rào cản mà là một lời mời - một cơ hội để điều tra chính xác mức độ khó của việc chứng minh các vấn đề khó. Các giấy trong đó họ đặt ra quan điểm mới này sẽ trở thành một trong những tác phẩm ban đầu có ảnh hưởng nhất trong lĩnh vực siêu phức tạp mới ra đời.

Bài báo của Kabanets và Cai đã nhấn mạnh một vấn đề tính toán tiềm ẩn trong công thức của Razborov và Rudich về hàng rào chứng minh tự nhiên: Đưa ra bảng chân lý của hàm Boolean, xác định xem nó có độ phức tạp mạch cao hay thấp. Họ gọi đây là vấn đề kích thước mạch tối thiểu, hay MCSP.

MCSP là một vấn đề siêu phức tạp tinh túy: một vấn đề tính toán có chủ đề không phải là lý thuyết đồ thị hoặc chủ đề bên ngoài khác, mà là chính lý thuyết phức tạp. Thật vậy, nó giống như một phiên bản định lượng của câu hỏi đã thúc đẩy các nhà lý thuyết về độ phức tạp giải quyết P so với NP bằng cách sử dụng phương pháp tiếp cận độ phức tạp của mạch vào những năm 1980: Hàm Boolean nào khó tính toán và hàm nào dễ tính?

“Nếu chúng tôi đưa ra một thuật toán MCSP, đó sẽ giống như một cách tự động hóa những gì chúng tôi đang làm trong lý thuyết phức tạp,” Impagliazzo nói. “Ít nhất nó cũng cho chúng tôi một cái nhìn sâu sắc về cách làm tốt hơn công việc của mình.”

Các nhà lý thuyết về độ phức tạp không lo lắng về việc thuật toán kỳ diệu này sẽ khiến họ thất bại - họ không nghĩ rằng nó tồn tại, bởi vì Razborov và Rudich đã chỉ ra rằng bất kỳ thuật toán nào như vậy để phân biệt các bảng chân lý có độ phức tạp cao với các bảng có độ phức tạp thấp sẽ tạo ra mật mã. không thể nào. Điều đó có nghĩa là MCSP có thể là một vấn đề tính toán khó. Nhưng nó khó đến mức nào? Nó có phải là NP-đầy đủ, giống như bài toán đường đi Hamilton và gần như mọi bài toán khác mà các nhà nghiên cứu đã phải vật lộn trong những năm 1960 không?

Đối với các vấn đề trong NP, "nó khó đến mức nào?" thường đủ dễ để trả lời, nhưng MCSP dường như là một ngoại lệ kỳ lạ. Kabanets nói: “Chúng tôi có rất ít bài toán 'lơ lửng' không liên quan đến hòn đảo bài toán NP-đầy đủ này, mặc dù chúng có vẻ khó.

Kabanets biết rằng anh và Cai không phải là những người đầu tiên xem xét vấn đề mà họ đặt tên là MCSP. Các nhà toán học Liên Xô đã nghiên cứu một vấn đề rất giống nhau bắt đầu từ những năm 1950, trong một nỗ lực ban đầu để hiểu được khó khăn nội tại của các vấn đề tính toán khác nhau. Leonid Levin đã vật lộn với nó trong khi phát triển thứ sẽ trở thành lý thuyết về tính đầy đủ của NP vào cuối những năm 1960, nhưng ông không thể chứng minh nó là NP-đầy đủ và ông đã xuất bản bài báo chuyên đề của mình mà không có nó.

Sau đó, vấn đề thu hút rất ít sự chú ý trong 30 năm, cho đến khi Kabanets và Cai ghi nhận mối liên hệ của nó với hàng rào bằng chứng tự nhiên. Kabanets không mong muốn tự mình giải quyết vấn đề — thay vào đó, anh ấy muốn khám phá lý do tại sao việc chứng minh rằng vấn đề có vẻ khó về độ cứng tính toán này thực sự khó đến vậy.

“Theo một nghĩa nào đó, đó là sự phức tạp meta-meta,” nói Rahul Santhanam, một nhà lý thuyết phức tạp tại Đại học Oxford.

Nhưng nó có phải là độ cứng hoàn toàn không, hay ít nhất có cách nào đó để hiểu tại sao các nhà nghiên cứu đã không thành công trong việc chứng minh rằng MCSP là NP-đầy đủ? Kabanets đã phát hiện ra rằng, vâng, có một lý do: Khó khăn trong việc hiểu độ phức tạp của mạch đóng vai trò như một rào cản đối với bất kỳ chiến lược đã biết nào để chứng minh tính đầy đủ NP của MCSP - một vấn đề tự nó là khó hiểu về độ phức tạp của mạch. Logic vặn vẹo, tự đánh bại bản thân của hàng rào bằng chứng tự nhiên dường như không thể tránh khỏi.

Cũng có thể MCSP không phải là NP-đầy đủ, nhưng điều đó cũng có vẻ khó xảy ra — một số biến thể đơn giản hơn của vấn đề đã được biết là NP-đầy đủ.

Impagliazzo nói: “Chúng tôi không có một nơi thích hợp để đặt nó liên quan trực tiếp đến tất cả các vấn đề khác mà chúng tôi nghiên cứu.

Kabanets đã làm sáng tỏ hành vi kỳ lạ của MCSP, nhưng anh ấy không biết làm thế nào để tiến bộ hơn nữa. Nghiên cứu siêu phức hợp chậm lại như một giọt nước. Nó sẽ phát triển trở lại 16 năm sau, khi các nhà nghiên cứu phát hiện ra mối liên hệ đáng ngạc nhiên với một câu hỏi cơ bản khác: Thật khó để giải quyết vấn đề nếu bạn chỉ quan tâm đến việc tìm ra câu trả lời đúng trong phần lớn thời gian?

War of the Worlds

Đối với các vấn đề hàng ngày, câu trả lời phù hợp với hầu hết thời gian thường là đủ tốt. Chẳng hạn, chúng tôi lên kế hoạch cho các tuyến đường đi làm của mình cho các kiểu giao thông điển hình, chứ không phải cho các tình huống xấu nhất.

Hầu hết các nhà lý thuyết về độ phức tạp khó thỏa mãn hơn: Họ chỉ bằng lòng tuyên bố một vấn đề dễ dàng nếu họ có thể tìm thấy một thuật toán nhanh có câu trả lời đúng cho mọi đầu vào có thể. Cách tiếp cận tiêu chuẩn đó phân loại các vấn đề theo cái mà các nhà nghiên cứu gọi là độ phức tạp “trường hợp xấu nhất”. Nhưng cũng có một lý thuyết về độ phức tạp của “trường hợp trung bình”, trong đó các vấn đề được coi là dễ nếu có một thuật toán nhanh nhận được câu trả lời đúng trên hầu hết các đầu vào.

Sự khác biệt quan trọng đối với các nhà mật mã học. Hãy tưởng tượng một vấn đề tính toán dễ giải quyết đối với hầu hết mọi đầu vào, ngoại trừ một số trường hợp khó giải quyết khi thuật toán tốt nhất không thành công. Lý thuyết về độ phức tạp trong trường hợp xấu nhất coi đó là một vấn đề khó, nhưng đối với mật mã thì nó vô dụng: Nếu chỉ một số thông điệp của bạn khó giải mã, thì có ích lợi gì?

Thực ra chính Levin là người đã khởi xướng nghiên cứu nghiêm ngặt về độ phức tạp của trường hợp trung bình, một thập kỷ sau công trình tiên phong của ông về tính đầy đủ của NP. Trong những năm gần đây, anh ta đã phải đối mặt với chính quyền Xô Viết - anh ta là một kẻ gây rối bất kính, thỉnh thoảng sẽ phá hoại các hoạt động yêu nước trong nhóm thanh niên Đảng Cộng sản của anh ta. Năm 1972, ông bị từ chối cấp bằng tiến sĩ vì những lý do chính trị rõ ràng.

Impagliazzo nói: “Để thành công ở Liên Xô với tư cách là một nhà nghiên cứu trẻ, bạn không thể quá cố chấp, và thật khó để tưởng tượng Leonid lại không cố chấp.

Levin di cư sang Hoa Kỳ vào năm 1978, và vào giữa những năm 1980, ông chuyển sự chú ý sang độ phức tạp của trường hợp trung bình. Ông bắt đầu làm việc với những người khác để phát triển lý thuyết hơn nữa, bao gồm cả Impagliazzo, một sinh viên mới tốt nghiệp vào thời điểm đó. Nhưng ngay cả khi họ đã đạt được tiến bộ, Impagliazzo nhận thấy rằng các nhà nghiên cứu thường nói chuyện qua loa với nhau. Anh ấy muốn mọi người cùng đồng quan điểm, và chẳng ích gì khi các bài báo của Levin nổi tiếng ngắn gọn - bài báo mà bắt đầu lĩnh vực này độ phức tạp của trường hợp trung bình dài chưa đầy hai trang.

“Tôi định dịch tác phẩm của Leonid sang những thuật ngữ kỹ thuật dễ tiếp cận hơn,” Impagliazzo nói. Anh ấy quyết định bắt đầu với một cái nhìn tổng quan ngắn gọn, vui tươi về bức tranh lớn trước khi đi sâu vào toán học. “Kiểu đó đã chiếm lĩnh tờ báo, và dù sao đó cũng là phần duy nhất mà mọi người còn nhớ.”

Sản phẩm giấy, xuất bản năm 1995, ngay lập tức trở thành tác phẩm kinh điển. Impagliazzo đã đặt ra những cái tên hay thay đổi cho năm thế giới được phân biệt bởi các mức độ khác nhau về độ cứng tính toán và khả năng mã hóa khác nhau. Chúng ta sống ở một trong những thế giới này, nhưng chúng ta không biết thế giới nào.

Kể từ khi bài báo của Impagliazzo xuất hiện, các nhà nghiên cứu đã mơ ước loại bỏ các phần trong đa vũ trụ thu nhỏ của ông — thu hẹp không gian khả năng bằng cách chứng minh rằng rốt cuộc một số thế giới không thể tồn tại. Hai thế giới là những mục tiêu đặc biệt hấp dẫn: những nơi không thể có mật mã mặc dù P ≠ NP.

Ở một trong những thế giới này, được gọi là Heuristica, tất cả các bài toán NP-đầy đủ đều dễ giải quyết trên hầu hết các đầu vào, nhưng các thuật toán nhanh đôi khi mắc lỗi, vì vậy những bài toán này vẫn được coi là khó theo tiêu chuẩn của lý thuyết về độ phức tạp trong trường hợp xấu nhất. Đây là thế giới mà mật mã là không thể vì hầu hết mọi mã đều dễ dàng bị bẻ khóa. Ở một thế giới khác, được gọi là Pessiland, mật mã là không thể vì một lý do khác: Mọi vấn đề đều khó khăn trong trường hợp trung bình, nhưng việc mã hóa một tin nhắn khiến nó không thể đọc được ngay cả đối với người nhận dự định.

Hai thế giới này hóa ra có mối liên hệ chặt chẽ với các vấn đề siêu phức tạp — đặc biệt, số phận của Heuristica có liên quan đến câu hỏi lâu nay về việc liệu MCSP có phải là NP-đầy đủ hay không. Câu hỏi đã làm Kabanets mê mẩn và khiến Levin bối rối từ rất lâu không chỉ đơn thuần là sự tò mò: Có cả một thế giới đang bị đe dọa.

Để loại trừ Heuristica, các nhà nghiên cứu sẽ phải thu gọn sự khác biệt giữa độ phức tạp của trường hợp xấu nhất và trường hợp trung bình - nghĩa là họ phải chứng minh rằng bất kỳ thuật toán giả định nào giải quyết chính xác một vấn đề NP-đầy đủ trên hầu hết các đầu vào đều có thể thực sự giải quyết được vấn đề đó. trong tất cả trường hợp. Loại kết nối này, được gọi là giảm trường hợp xấu nhất đến trường hợp trung bình, được biết là tồn tại đối với một số vấn đề nhất định, nhưng không có vấn đề nào trong số đó là NP-đầy đủ, vì vậy những kết quả đó không ngụ ý điều gì tổng quát hơn. Việc loại bỏ Heuristica sẽ đưa các nhà mật mã học đi được nửa chặng đường để hiện thực hóa giấc mơ mã hóa an toàn dựa trên giả định duy nhất rằng P ≠ NP.

Nhưng phá hủy một thế giới không phải là một chiến công nhỏ. Năm 2003, hai nhà lý thuyết phức tạp cho thấy rằng các phương pháp hiện có để chứng minh mức giảm trường hợp xấu nhất thành trường hợp trung bình đối với các vấn đề NP-đầy đủ đã biết sẽ dẫn đến những hậu quả kỳ lạ, cho thấy rằng những bằng chứng như vậy có thể không khả thi.

Các nhà nghiên cứu sẽ phải tìm một cách tiếp cận khác, và bây giờ họ nghĩ rằng MCSP có thể chính là vấn đề họ cần. Nhưng điều đó sẽ không trở nên rõ ràng trong hơn một thập kỷ. Cái nhìn đầu tiên về mối liên hệ xuất hiện từ niềm đam mê dai dẳng của Marco Carmosino với hàng rào bằng chứng tự nhiên.

Carmosino lần đầu tiên bắt gặp nghiên cứu siêu phức tạp khi còn là một sinh viên tốt nghiệp thông qua một giấy 2013 của Kabanets và bốn nhà nghiên cứu khác, họ đã phát triển thêm cách tiếp cận hàng rào bằng chứng tự nhiên mà Kabanets đã đi tiên phong hơn một thập kỷ trước đó. Nó chỉ củng cố niềm tin của ông rằng vẫn còn nhiều điều cần học hỏi từ bài báo kinh điển của Razborov và Rudich.

Carmosino nói: “Lúc đó tôi bị ám ảnh bởi tờ báo đó. "Không có gì thay đổi."

Nỗi ám ảnh cuối cùng đã đơm hoa kết trái trong chuyến thăm một hội thảo kéo dài một học kỳ tại Đại học California, Berkeley, nơi anh dành phần lớn thời gian để nói chuyện với Impagliazzo, Kabanets và Antonina Kolokolova, một nhà lý thuyết phức tạp tại Đại học Tưởng niệm Newfoundland, người đã hợp tác với Kabanets trong bài báo năm 2013. Carmosino đã từng làm việc với ba người họ trước đây và sự hợp tác thành công đó đã giúp anh ấy tự tin đặt cho họ những câu hỏi về chủ đề khiến anh ấy hứng thú nhất.

Kabanets nhớ lại: “Anh ấy đã làm phiền mọi người theo cách tốt.

Lúc đầu, Carmosino có những ý tưởng mới để chứng minh tính đầy đủ NP cho phiên bản MCSP đã xuất hiện trong bài báo của Razborov và Rudich về hàng rào chứng minh tự nhiên. Nhưng những ý tưởng đó đã không thành công. Thay vào đó, một nhận xét ngẫu hứng của Impagliazzo đã khiến bốn nhà nghiên cứu nhận ra rằng rào cản bằng chứng tự nhiên có thể mang lại nhiều thuật toán mạnh mẽ hơn bất kỳ ai từng nhận ra — có một bản đồ bí mật được khắc vào rào cản.

Trong một giấy 2016, bốn nhà nghiên cứu đã chứng minh rằng một loại thuật toán MCSP trường hợp trung bình nhất định có thể được sử dụng để xây dựng thuật toán trường hợp xấu nhất nhằm xác định các mẫu ẩn trong các chuỗi chữ số trông ngẫu nhiên — một nhiệm vụ mà các nhà khoa học máy tính gọi là “học tập”. Đó là một kết quả nổi bật vì việc học bằng trực giác có vẻ khó hơn so với nhiệm vụ phân loại nhị phân — độ phức tạp cao hoặc độ phức tạp thấp — do thuật toán MCSP thực hiện. Và thật ngạc nhiên, nó đã liên kết mức độ phức tạp trong trường hợp xấu nhất của một nhiệm vụ với mức độ phức tạp trong trường hợp trung bình của nhiệm vụ kia.

Impagliazzo nói: “Rõ ràng là một kết nối như vậy sẽ tồn tại.

Một thuật toán nhanh cho MCSP hoàn toàn là giả thuyết đối với các mạch Boolean chung: Nó không thể tồn tại trừ khi MCSP trở thành một vấn đề tính toán dễ dàng, bất chấp mọi bằng chứng ngược lại, và điều đó có nghĩa là thuật toán học được ngụ ý trong bài báo của bốn nhà nghiên cứu là giả thiết như nhau.

Nhưng đối với một số phiên bản đơn giản hơn của MCSP — phân biệt bảng chân lý có độ phức tạp cao với bảng chân lý có độ phức tạp thấp khi có các hạn chế cụ thể đối với mạch — thuật toán nhanh đã được biết đến trong nhiều năm. Bài báo của Carmosino, Impagliazzo, Kabanets và Kolokolova đã chỉ ra rằng các thuật toán này có thể được chuyển đổi thành các thuật toán học tập cũng bị hạn chế tương tự nhưng vẫn mạnh hơn bất kỳ thuật toán nào mà các nhà nghiên cứu đã hiểu trước đây ở cấp độ lý thuyết chặt chẽ như vậy.

Ilango nói: “Bằng cách nào đó, hương vị tự quy chiếu của chúng cho phép bạn làm những việc mà dường như bạn không thể làm được với những bài toán tiêu chuẩn hơn.

Kết quả đã thu hút sự chú ý của các nhà lý thuyết phức tạp làm việc về các chủ đề khác. Nó cũng là bản xem trước của các mối liên hệ xa hơn giữa độ phức tạp meta và độ phức tạp của trường hợp trung bình sẽ xuất hiện trong những năm tới.

Trên hết, đó là minh chứng cho việc các nhà nghiên cứu có thể tiến xa đến mức nào bằng cách đặt những câu hỏi đơn giản về những rào cản thoạt đầu dường như chỉ cản trở tiến trình của họ.

Impagliazzo nói: “Loại tính hai mặt này là chủ đề xuyên suốt ít nhất 30 hoặc 40 năm phức tạp vừa qua. “Những trở ngại thường là những cơ hội.”

Tín dụng từng phần

Tiến độ chỉ tăng tốc trong những năm kể từ khi Carmosino và các đồng nghiệp của ông xuất bản bài báo của họ.

“Những điều mới đang xảy ra,” Kolokolova nói. “Có rất nhiều nhà nghiên cứu trẻ thực sự, thực sự sáng giá.”

Ilango là một trong những nhà nghiên cứu trẻ tuổi này — trong ba năm đầu tiên ở trường sau đại học, anh ấy đã tấn công vào vấn đề mở khó khăn là chứng minh MCSP NP-đầy đủ bằng cách sử dụng chiến lược hai hướng: chứng minh NP-đầy đủ cho đơn giản phiên bản của MCSP, như các nhà nghiên cứu về độ phức tạp của mạch đã làm khi tấn công P so với NP vào những năm 1980, đồng thời chứng minh tính đầy đủ của NP cho phiên bản phức tạp hơn, trực giác có vẻ khó hơn và do đó có lẽ dễ chứng minh khó hơn.

Ilango ghi nhận sự quan tâm của mình đối với siêu phức tạp đối với Eric Allen, một nhà lý thuyết phức hợp tại Đại học Rutgers và là một trong số ít các nhà nghiên cứu tiếp tục nghiên cứu về siêu phức hợp trong những năm 2000 và đầu những năm 2010. Ilango nói: “Sự nhiệt tình của anh ấy rất dễ lây lan.

Một nhà nghiên cứu trẻ khác được truyền cảm hứng bởi Allender là Hirahara Shuichi, hiện là giáo sư tại Viện Tin học Quốc gia ở Tokyo. Khi vẫn còn là một sinh viên tốt nghiệp vào năm 2018, Hirahara đã tiết lộ mức độ thực sự của mối quan hệ giữa độ phức tạp meta và độ phức tạp trường hợp trung bình mà Carmosino và các đồng tác giả của ông đã phát hiện ra. Bốn nhà nghiên cứu đó đã tìm thấy mối liên hệ giữa độ phức tạp trong trường hợp trung bình của một vấn đề - MCSP - và độ phức tạp trong trường hợp xấu nhất của vấn đề khác - học Boolean. Hirahara đã phát triển kỹ thuật của họ hơn nữa để lấy được giảm trường hợp xấu nhất đến trường hợp trung bình cho MCSP. Kết quả của ông ngụ ý rằng một thuật toán MCSP trường hợp trung bình giả định giống như thuật toán mà Carmosino và các đồng nghiệp của ông đã xem xét sẽ thực sự đủ mạnh để giải quyết một phiên bản MCSP hơi khác một chút mà không mắc bất kỳ lỗi nào.

Kết quả của Hirahara rất thú vị vì nhiều nhà nghiên cứu nghi ngờ rằng MCSP là NP-đầy đủ, không giống như tất cả các bài toán khác đã biết mức giảm từ trường hợp xấu nhất đến trường hợp trung bình. Nếu họ có thể mở rộng kết quả của Hirahara để bao gồm tất cả các thuật toán trường hợp trung bình và sau đó chứng minh rằng MCSP là NP-đầy đủ, điều đó sẽ chứng tỏ chúng ta không sống ở Heuristica.

“Đó thực sự sẽ là một kết quả chấn động trái đất,” Santhanam nói.

Việc chứng minh rằng MCSP là NP-đầy đủ có vẻ như là một yêu cầu cao - xét cho cùng, câu hỏi đã được mở trong hơn 50 năm. Nhưng sau một bước đột phá năm ngoái của Hirahara, các nhà nghiên cứu hiện đang ở gần hơn nhiều so với bất kỳ ai mong đợi vài năm trước.

Hirahara đã chứng minh NP-đầy đủ cho một biến thể của bài toán được gọi là MCSP từng phần, trong đó bạn bỏ qua một số mục nhất định trong mỗi bảng chân lý. Bằng chứng của ông được xây dựng dựa trên các phương pháp do Ilango phát triển để chỉ ra rằng một phần MCSP tương đương với một vấn đề dường như không liên quan đến một kỹ thuật mã hóa được gọi là chia sẻ bí mật. Đây là một cách để phân chia một tin nhắn được mã hóa cho nhiều người để nó chỉ có thể được giải mã nếu một phần nhất định trong số họ làm việc cùng nhau.

Đối với bất kỳ ứng dụng thực tế nào trong mật mã, bạn muốn biết trước phần đó, nhưng với sự trợ giúp của các thủ thuật mật mã bổ sung, bạn có thể xây dựng một kịch bản khó chịu trong đó thật khó để tìm ra có bao nhiêu người cần hợp tác. Hirahara đã tìm ra cách để chứng minh rằng vấn đề mã hóa giả tạo này là NP-đầy đủ và sau đó chỉ ra rằng bằng chứng cũng ngụ ý tính đầy đủ NP của một phần MCSP.

Kết quả này đã tiếp thêm năng lượng cho các nhà nghiên cứu về siêu phức hợp thậm chí còn nhiều hơn cả công trình trước đây của Hirahara, và các nhà nghiên cứu khác cũng chú ý đến — nhà lý thuyết phức tạp và blogger Lance Fortnow gọi nó là kết quả của năm. Đó là bởi vì việc giải quyết các phiên bản “chức năng một phần” như vậy của các vấn đề tính toán là một bước trung gian quan trọng trong các bằng chứng về tính đầy đủ của NP khác.

“Đó là công việc tuyệt vời,” Williams nói. “Mọi người đều nghĩ rằng những bài toán từng phần này có độ khó gần giống như bài toán đầy đủ.”

Các trở ngại vẫn còn để chứng minh tính đầy đủ của NP cho phiên bản đầy đủ của MCSP. Nhưng không có loại rào cản nào gợi ý rằng cần có một bộ công cụ hoàn toàn mới — vấn đề có thể chỉ là tìm ra cách phù hợp để kết hợp các kỹ thuật đã biết. Một bằng chứng cuối cùng sẽ giải quyết tình trạng của một trong số ít các vấn đề đã chống lại sự phân loại chừng nào lý thuyết phức tạp còn tồn tại. Qua email, Levin viết: “Tôi thật khiêm tốn khi chứng tỏ rằng mình thật ngu ngốc khi không thể nhìn thấy nó :-).”

Những mảnh ghép còn thiếu

MCSP thậm chí không phải là vấn đề siêu phức tạp duy nhất đã thúc đẩy một bước đột phá lớn. Vào năm 2020, nhà mật mã học của Cornell Tech Đèo Rafael và sinh viên tốt nghiệp của mình Yanyi Liu phát hiện ra một kết nối giữa một vấn đề siêu phức tạp khác và một giao thức mã hóa cơ bản xác định ranh giới giữa Heuristica và Pessiland, điều tồi tệ nhất trong thế giới của Impagliazzo (trong đó các vấn đề về NP-đầy đủ là khó theo nghĩa trung bình nhưng mã hóa vẫn không thể thực hiện được). Điều đó làm cho vấn đề mà họ nghiên cứu trở thành một ứng cử viên hàng đầu cho một cuộc tấn công vào Pessiland, và công việc gần đây hơn chỉ ra rằng nó cũng có thể hoạt động chống lại Heuristica.

“Các mảnh ghép khác nhau bị thiếu,” Pass nói. “Đối với tôi, thật kỳ diệu khi những lĩnh vực này được kết nối mật thiết đến vậy.”

Hirahara cảnh báo rằng những thách thức vẫn đang chờ đợi các nhà nghiên cứu có ý định loại bỏ các thế giới mà Impagliazzo gợi lên 30 năm trước. “Tôi muốn nói rằng đến một lúc nào đó Heuristica và Pessiland sẽ bị loại trừ, nhưng tôi không chắc chúng ta thân thiết đến mức nào,” anh ấy nói.

Nhiều nhà nghiên cứu cho rằng khó khăn lớn nhất sẽ là thu hẹp khoảng cách dường như vô thưởng vô phạt giữa hai mô hình khác nhau về độ phức tạp của trường hợp trung bình. Các nhà mật mã học thường nghiên cứu các thuật toán trường hợp trung bình mắc lỗi theo cả hai hướng, đôi khi đánh dấu nhầm các chuỗi ngẫu nhiên thành chuỗi giả ngẫu nhiên và ngược lại. Trong khi đó, việc giảm trường hợp xấu nhất thành trường hợp trung bình của Hirahara hoạt động cho các thuật toán trường hợp trung bình chỉ tạo ra loại lỗi đầu tiên. Những khác biệt tinh tế như thế này có thể tạo ra một thế giới khác biệt trong lý thuyết phức tạp. Nhưng bất chấp rào cản này và nhiều rào cản khác, Allender không thể không bày tỏ sự lạc quan thận trọng.

Ông nói: “Tôi cố gắng không để mình quá tin tưởng bởi vì có một hồ sơ theo dõi khá rõ ràng về việc không có gì hiệu quả. “Nhưng chúng ta đang chứng kiến ​​rất nhiều sự phát triển thực sự thú vị — những cách để vượt qua những thứ trông giống như rào cản.”

Nếu có một bài học mà các nhà nghiên cứu đã học được từ cuộc đấu tranh của họ để trả lời câu hỏi P so với NP - hoặc thậm chí chỉ cần hiểu nó - thì đó là lý thuyết phức tạp tự nó phức tạp. Nhưng thử thách đó chính xác là điều làm cho nhiệm vụ trở nên bổ ích.

Carmosino nói: “Thực sự là một điều tuyệt vời khi nó quá khó. “Tôi sẽ không bao giờ cảm thấy buồn chán.”

Ghi chú của biên tập viên: Scott Aaronson là thành viên của Tạp chí Quanta'S bảng điều khiển.