Không phải lúc nào trẻ 5 tuổi cũng có thể nắm bắt được các câu hỏi ở lĩnh vực khoa học máy tính, nhưng điều đó vẫn có thể xảy ra. Ví dụ, giả sử một học sinh mẫu giáo tên Alice có hai quả táo, nhưng cô ấy thích cam hơn. May mắn thay, các bạn cùng lớp của cô đã phát triển một hệ thống buôn bán trái cây lành mạnh với tỷ giá hối đoái được thực thi nghiêm ngặt: Chẳng hạn, từ bỏ một quả táo và bạn có thể nhận được một quả chuối. Liệu Alice có thể thực hiện một loạt giao dịch bằng cách nhặt và dỡ chuối hoặc dưa đỏ để đưa cô ấy đến loại trái cây yêu thích của mình không?

Nghe có vẻ đơn giản. “Bạn có thể đến trường tiểu học và kể điều đó cho trẻ em,” nói Christoph Haase, một nhà khoa học máy tính tại Đại học Oxford. “Mọi người sẽ nghĩ, 'Điều đó hẳn là dễ dàng.'”

Nhưng vấn đề toán học ẩn sau tình thế tiến thoái lưỡng nan của Alice - được gọi là vấn đề về khả năng tiếp cận đối với các hệ thống cộng vectơ - lại tinh tế một cách đáng ngạc nhiên. Trong khi một số trường hợp có thể được giải quyết dễ dàng thì các nhà khoa học máy tính đã phải vật lộn trong gần nửa thế kỷ để phát triển sự hiểu biết toàn diện về vấn đề này. Giờ đây, trong một loạt đột phá trong vài năm qua, họ đã xác định chắc chắn rằng vấn đề đó có thể phức tạp đến mức nào.

Hóa ra vấn đề trẻ thơ này lại phức tạp một cách vô lý, gần như phức tạp như trong phim hoạt hình - phức tạp đến mức thực tế là tất cả các vấn đề khác đều có thể xảy ra. những vấn đề tính toán nổi tiếng khó khăn trông giống như trò chơi trẻ con. Hãy cố gắng định lượng nỗ lực cần thiết để giải quyết vấn đề này và bạn sẽ sớm phải đối mặt với những con số lớn đến mức ngay cả việc đếm các chữ số của chúng cũng sẽ giúp bạn đạt được những con số mà bạn chưa từng nghe đến. Những con số như vậy thường gợi ra sự so sánh về quy mô của vũ trụ, nhưng ngay cả những sự so sánh đó cũng không thể thực hiện được. “Điều đó sẽ không công bằng,” nói Georg Zetzsche, một nhà khoa học máy tính tại Viện Hệ thống Phần mềm Max Planck ở Kaiserslautern, Đức. “Vũ trụ thật nhỏ bé.”

Trong tầm với?

Bỏ qua bản chất của nó, vấn đề về khả năng tiếp cận là về các đối tượng toán học được gọi là vectơ, là danh sách các số có thứ tự. Các mục trong danh sách này được gọi là thành phần và số lượng thành phần trong một vectơ được gọi là số chiều của nó. Ví dụ: kho trái cây của Alice có thể được mô tả bằng vectơ bốn chiều (a, b, c, d), các thành phần của nó đại diện cho số lượng táo, chuối, dưa đỏ và cam mà cô ấy có tại bất kỳ thời điểm nào.

Hệ thống cộng vectơ, hay VAS, là tập hợp các vectơ biểu thị sự chuyển đổi có thể có giữa các trạng thái trong một hệ thống. Đối với Alice, vectơ chuyển tiếp (−1, −1, 1, 0) sẽ biểu thị sự trao đổi một quả táo và một quả chuối lấy một quả dưa đỏ. Vấn đề về khả năng tiếp cận VAS hỏi liệu có bất kỳ sự kết hợp nào của các chuyển đổi được phép có thể đưa bạn từ trạng thái ban đầu cụ thể đến trạng thái mục tiêu cụ thể hay không - hoặc theo thuật ngữ toán học, liệu có bất kỳ tổng vectơ chuyển tiếp nào biến vectơ bắt đầu thành vectơ đích hay không. Chỉ có một nhược điểm: Không thành phần nào của vectơ mô tả trạng thái của hệ thống có thể giảm xuống dưới XNUMX.

“Đó là một hạn chế rất tự nhiên đối với một mô hình thực tế,” nói Wojciech Czerwiński, một nhà khoa học máy tính tại Đại học Warsaw. “Bạn không thể có số táo âm.”

Trong một số hệ thống, thật dễ dàng để xác định liệu vectơ mục tiêu có thể truy cập được hay không. Nhưng điều đó không phải lúc nào cũng đúng. Các nhà khoa học máy tính quan tâm nhất đến các hệ thống cộng vectơ có vẻ ngoài đơn giản, trong đó việc xác định khả năng tiếp cận khó đến mức nào. Để nghiên cứu những trường hợp đó, các nhà nghiên cứu bắt đầu bằng việc xác định một con số định lượng quy mô của một hệ thống nhất định. Con số này, được biểu thị bằng n, bao gồm số chiều, số lần chuyển tiếp và các yếu tố khác. Sau đó, họ hỏi độ khó của vấn đề về khả năng tiếp cận có thể tăng nhanh như thế nào khi n ngày càng lớn hơn.

Để trả lời câu hỏi đó, các nhà nghiên cứu sử dụng hai phương pháp bổ sung cho nhau. Đầu tiên, họ tìm kiếm các ví dụ về các hệ thống cộng vectơ đặc biệt phức tạp trong đó việc xác định khả năng tiếp cận đòi hỏi một số nỗ lực tối thiểu. Những mức tối thiểu đó được gọi là “giới hạn dưới” về mức độ phức tạp của vấn đề - họ nói với các nhà nghiên cứu, “Các hệ thống phức tạp nhất cho một tình huống nhất định n ít nhất cũng khó thế này.”

Thứ hai, các nhà nghiên cứu cố gắng thiết lập “giới hạn trên” - giới hạn về mức độ khó tiếp cận, ngay cả trong những hệ thống ma quỷ nhất. Những người này nói, “Những trường hợp khó khăn nhất đối với một tình huống nhất định n cùng lắm là khó thế này.” Để xác định chính xác mức độ khó tiếp cận trong các hệ thống phức tạp nhất, các nhà nghiên cứu thử đẩy giới hạn dưới lên và giới hạn trên xuống cho đến khi chúng gặp nhau.

Thứ của cơn ác mộng

Hệ thống cộng vector có lịch sử lâu đời. Từ những năm 1960, các nhà khoa học máy tính đã sử dụng chúng để lập mô hình các chương trình chia tính toán thành nhiều phần nhỏ và xử lý đồng thời trên các phần đó. Loại “điện toán đồng thời” này hiện nay rất phổ biến nhưng các nhà nghiên cứu vẫn chưa hiểu đầy đủ về nền tảng toán học của nó.

Năm 1976, nhà khoa học máy tính Richard Lipton đã thực hiện bước đầu tiên để hiểu được mức độ phức tạp của vấn đề về khả năng tiếp cận VAS. Ông đã phát triển một quy trình xây dựng các hệ thống trong đó cách nhanh nhất để xác định liệu một trạng thái có thể tiếp cận được từ một trạng thái khác hay không là vạch ra một chuỗi các chuyển đổi giữa chúng. Điều đó cho phép anh ta sử dụng độ dài của con đường ngắn nhất giữa hai trạng thái được lựa chọn cẩn thận làm thước đo độ khó của bài toán khả năng tiếp cận.

Lipton thì chứng minh anh ấy có thể xây dựng một hệ thống có kích thước n trong đó đường đi ngắn nhất giữa hai trạng thái có nhiều hơn $latex 2^{2^n}$ chuyển tiếp. Điều đó ngụ ý giới hạn dưới cấp số nhân gấp đôi tương ứng đối với nỗ lực cần thiết để xác định khả năng tiếp cận trong hệ thống của anh ấy. Đó là một khám phá đáng kinh ngạc - sự tăng trưởng gấp đôi theo cấp số nhân là cơn ác mộng của các nhà khoa học máy tính. Thật vậy, các nhà nghiên cứu thường chùn bước ngay cả với mức tăng trưởng theo cấp số nhân thông thường, con số này không thể so sánh được: $latex {2^5}= 32$, nhưng $latex 2^{2^5}$ là hơn 4 tỷ.

Hầu hết các nhà nghiên cứu cho rằng Lipton đã tạo ra các hệ thống cộng vectơ phức tạp nhất có thể, nghĩa là ông đã nâng giới hạn dưới lên cao nhất có thể. Trong trường hợp đó, điều duy nhất còn thiếu sẽ là giới hạn trên đi kèm với nó - tức là bằng chứng cho thấy không thể có hệ thống nào trong đó việc xác định khả năng tiếp cận thậm chí còn khó hơn. Nhưng không ai biết cách chứng minh điều đó. Nhà khoa học máy tính Ernst Mayr đến gần nhất khi ông chứng minh vào năm 1981 rằng về nguyên tắc, luôn có thể xác định được khả năng tiếp cận trong bất kỳ hệ thống cộng vectơ nào. Nhưng bằng chứng của ông không đưa ra bất kỳ giới hạn định lượng nào về mức độ khó của vấn đề. Có một tầng, nhưng không có trần nhà.

“Tôi chắc chắn đã nghĩ về điều đó nhiều lần,” Lipton nói. “Nhưng sau một thời gian, tôi đã bỏ cuộc, và theo những gì tôi có thể nói, không ai đạt được tiến bộ nào trong suốt 40 năm.”

Năm 2015, các nhà khoa học máy tính Jérôme Leroux và Sylvain Schmitz cuối cùng đã được thành lập giới hạn trên về mặt định lượng - một mức cao đến mức các nhà nghiên cứu cho rằng đó chỉ là bước đầu tiên có thể bị đẩy xuống để đáp ứng giới hạn dưới của Lipton.

Nhưng đó không phải là điều đã xảy ra. Vào năm 2019, các nhà nghiên cứu đã phát hiện ra giới hạn dưới cao hơn nhiều so với giới hạn của Lipton, đảo ngược quan niệm thông thường hàng thập kỷ. Vấn đề về khả năng tiếp cận VAS phức tạp hơn nhiều so với những gì mọi người dự đoán.

Tháp quyền lực

Kết quả gây sốc năm 2019 bắt nguồn từ thất bại. Năm 2018, Czerwiński đã bác bỏ phỏng đoán của Leroux và Filip Mazowiecki, một nhà khoa học máy tính hiện đang làm việc tại Đại học Warsaw, điều đó sẽ giúp đạt được tiến bộ trong một vấn đề liên quan. Trong các cuộc thảo luận tiếp theo, các nhà nghiên cứu đã tìm ra một phương pháp mới đầy hứa hẹn để xây dựng các hệ thống cộng vectơ cực kỳ phức tạp, có thể hàm ý một giới hạn thấp hơn mới đối với vấn đề về khả năng tiếp cận VAS, nơi tiến độ đã bị đình trệ quá lâu.

“Mọi thứ trong tâm trí tôi đều kết nối với khả năng tiếp cận VAS,” Czerwiński nhớ lại. Trong một học kỳ với khối lượng giảng dạy nhẹ nhàng, anh quyết định tập trung hoàn toàn vào vấn đề đó, cùng với Leroux, Mazowiecki và hai nhà nghiên cứu khác — Sławomir Lasota của Đại học Warsaw và Ranko Lazić của Đại học Warwick.

Sau vài tháng, nỗ lực của họ đã được đền đáp. Czerwiński và các cộng sự chứng minh rằng họ có thể xây dựng các hệ thống cộng vectơ trong đó đường đi ngắn nhất giữa hai trạng thái có liên quan đến kích thước của hệ thống bằng một phép toán gọi là túc thừa khiến cho sự tăng trưởng theo cấp số nhân gấp đôi thậm chí là ác mộng dường như đã được chế ngự.

Phép lặp thừa là một phần mở rộng đơn giản của một mẫu kết nối các phép toán quen thuộc nhất trong toán học, bắt đầu bằng phép cộng. Gắn với nhau n bản sao của một số và kết quả tương đương với việc nhân số đó với n. Nếu bạn nhân với nhau n bản sao của một số, tương đương với phép lũy thừa hoặc nâng số đó lên nsức mạnh thứ. Phép lặp thừa, thường được biểu thị bằng một cặp mũi tên hướng lên, là bước tiếp theo trong trình tự này: Xếp lại một số bằng n có nghĩa là lũy thừa nó n nhiều lần để tạo ra một tháp quyền lực n câu chuyện cao.

Thật khó để hiểu được rằng thừa kế nhanh chóng vượt quá tầm kiểm soát của bạn như thế nào: $latex 2 uparrowuparrow 3$, hoặc $latex 2^{2^2}$, là 16, $latex 2 uparrowuparrow 4$ chỉ hơn 65,000 và $latex 2 uparrowuparrow 5$ là một số có gần 20,000 chữ số. Về mặt vật lý, không thể viết ra tất cả các chữ số của $latex 2 uparrowuparrow 6$ - một trách nhiệm phải sống trong một vũ trụ nhỏ như vậy.

Trong kết quả mang tính bước ngoặt của họ, Czerwiński và các đồng nghiệp của ông đã chứng minh rằng tồn tại các hệ thống cộng vectơ có kích thước n trong đó cách tốt nhất để xác định khả năng tiếp cận là vạch ra một đường dẫn bao gồm nhiều chuyển đổi $latex 2 uparrowuparrow n$, ngụ ý một giới hạn dưới mới làm giảm đi giới hạn của Lipton. Nhưng dù choáng váng đến mức nào, nó vẫn chưa phải là quyết định cuối cùng về mức độ phức tạp của vấn đề.

Đến Quinquagintillion và hơn thế nữa 

Chỉ vài tháng sau giới hạn dưới mới gây sốc về mức độ phức tạp của khả năng tiếp cận VAS, Leroux và Schmitz đẩy xuống giới hạn trên mà họ đã thiết lập ba năm trước, nhưng họ vẫn chưa đạt tới mức thừa phân. Thay vào đó, họ đã chứng minh rằng độ phức tạp của vấn đề về khả năng tiếp cận không thể tăng nhanh hơn một vấn đề toán học quái dị gọi là hàm Ackermann.

Để hiểu được chức năng đó, hãy lấy mẫu được sử dụng để xác định túc thừa cho đến kết luận nghiệt ngã của nó. Hoạt động tiếp theo trong chuỗi, được gọi là pentation, thể hiện phép lặp lặp lại; tiếp theo là một thao tác khác (hexation) để lặp lại pentation, v.v.

Hàm Ackermann, ký hiệu là $latex A(n)$, là những gì bạn nhận được khi di chuyển một bước lên bậc thang phép toán này với mỗi điểm dừng trên trục số: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$, v.v. Bản thân số chữ số trong $latex A(4)$ là một con số khổng lồ xấp xỉ bằng 1 quiquagintillion — đó là cái tên kỳ lạ và hiếm khi cần thiết cho số 1 theo sau là 153 số 5. “Đừng lo lắng về Ackermann số XNUMX,” khuyên Javier Esparza, một nhà khoa học máy tính tại Đại học Kỹ thuật Munich.

Kết quả của Leroux và Schmitz để lại một khoảng cách lớn giữa giới hạn dưới và giới hạn trên - độ phức tạp chính xác của vấn đề về khả năng tiếp cận VAS có thể nằm ở một trong hai đầu của phạm vi hoặc bất kỳ vị trí nào ở giữa. Czerwiński không có ý định để khoảng cách đó tồn tại. “Chúng tôi tiếp tục làm việc này vì rõ ràng đó là điều lớn nhất chúng tôi từng làm trong đời,” anh nói.

Bước đột phá cuối cùng đến vào năm 2021, khi Czerwiński đang cố vấn cho một sinh viên đại học năm thứ hai tên là Łukasz Orlikowski. Ông giao cho Orlikowski một biến thể đơn giản của bài toán để giúp anh ta bắt kịp tốc độ và công việc của Orlikowski đã giúp hai người họ phát triển một kỹ thuật mới cũng có thể áp dụng cho bài toán về khả năng tiếp cận chung. Điều đó đã cho phép họ nâng giới hạn dưới về cơ bản - cho đến tận giới hạn trên Ackermann của Leroux và Schmitz. Làm việc độc lập, Leroux có được một kết quả tương đương khoảng thời gian đó

Cuối cùng, các nhà nghiên cứu đã xác định được mức độ phức tạp thực sự của vấn đề về khả năng tiếp cận. Giới hạn dưới của Czerwiński, Orlikowski và Leroux cho thấy rằng có một chuỗi các hệ thống cộng vectơ lớn dần trong đó đường đi ngắn nhất giữa hai trạng thái tăng tỷ lệ với hàm Ackermann. Giới hạn trên của Leroux và Schmitz cho thấy rằng vấn đề về khả năng tiếp cận không thể phức tạp hơn thế - một niềm an ủi nhỏ cho bất kỳ ai đang hy vọng vào một quy trình thực tế không thể sai lầm để giải quyết nó. Đó là một minh họa nổi bật về mức độ tinh tế của các vấn đề tính toán tưởng chừng như đơn giản.

Chưa bao giờ hoàn thành

Các nhà nghiên cứu đã tiếp tục nghiên cứu vấn đề về khả năng tiếp cận VAS sau khi xác định độ phức tạp chính xác của nó, vì nhiều biến thể của câu hỏi vẫn chưa được trả lời. Ví dụ, giới hạn trên và giới hạn dưới của Ackermann không phân biệt giữa các cách tăng khác nhau n, chẳng hạn như tăng số chiều của vectơ hoặc tăng số lượng chuyển tiếp được phép.

Gần đây, Czerwiński và các đồng nghiệp của ông đã tiến độ thực hiện giải thích những hiệu ứng khác biệt này bằng cách nghiên cứu mức độ phức tạp có thể tăng nhanh như thế nào trong các biến thể của hệ thống cộng vectơ có chiều cố định. Nhưng vẫn còn nhiều việc phải làm - ngay cả trong không gian ba chiều, nơi các hệ thống cộng vectơ dễ hình dung, độ phức tạp chính xác của vấn đề khả năng tiếp cận vẫn chưa được biết.

Mazowiecki nói: “Theo một cách nào đó, điều đó thật đáng xấu hổ đối với chúng tôi.

Các nhà nghiên cứu hy vọng rằng sự hiểu biết tốt hơn về các trường hợp tương đối đơn giản sẽ giúp họ phát triển các công cụ mới để nghiên cứu các mô hình tính toán khác phức tạp hơn các hệ thống cộng vectơ. Hiện tại, chúng ta hầu như không biết gì về những mô hình phức tạp hơn này.

Zetzsche nói: “Tôi xem đây là một phần của nhiệm vụ rất cơ bản nhằm hiểu được khả năng tính toán.

Quanta đang tiến hành một loạt cuộc khảo sát để phục vụ khán giả của chúng tôi tốt hơn. Lấy của chúng tôi khảo sát độc giả khoa học máy tính và bạn sẽ được tham gia để giành chiến thắng miễn phí Quanta hàng hóa.