Các nhà toán học hoàn thành nhiệm vụ xây dựng 'khối cầu'

Vào thế kỷ thứ tư, nhà toán học người Hy Lạp Pappus ở Alexandria đã ca ngợi những con ong vì “sự tiên liệu về mặt hình học” của chúng. Cấu trúc lục giác của tổ ong của chúng dường như là cách tối ưu để phân chia không gian hai chiều thành các ô có diện tích bằng nhau và chu vi tối thiểu — cho phép côn trùng cắt giảm lượng sáp chúng cần sản xuất, đồng thời tốn ít thời gian và năng lượng hơn để xây dựng tổ ong của chúng. tổ ong.

Hoặc đó là giả thuyết của Pappus và những người khác. Trong nhiều thiên niên kỷ, không ai có thể chứng minh rằng hình lục giác là tối ưu — cho đến cuối cùng, vào năm 1999, nhà toán học Thomas Hales đã chỉ ra rằng không có hình dạng nào khác có thể làm tốt hơn. Ngày nay, các nhà toán học vẫn chưa biết hình nào có thể xếp ba chiều trở lên với diện tích bề mặt nhỏ nhất có thể.

Bài toán “bọt” này hóa ra có nhiều ứng dụng — dành cho các nhà vật lý nghiên cứu hành vi của bong bóng xà phòng (hoặc bọt) và các nhà hóa học phân tích cấu trúc tinh thể, dành cho các nhà toán học khám phá sự sắp xếp khối cầu và các nhà thống kê phát triển các kỹ thuật xử lý dữ liệu hiệu quả .

Vào giữa những năm 2000, một công thức cụ thể của bài toán bọt cũng lọt vào mắt xanh của các nhà khoa học máy tính lý thuyết, họ đã ngạc nhiên phát hiện ra rằng nó có mối liên hệ sâu sắc với một bài toán mở quan trọng trong lĩnh vực của họ. Họ đã có thể sử dụng kết nối đó để tìm ra một hình dạng chiều cao mới với diện tích bề mặt tối thiểu.

"Tôi thích điều này qua lại," nói Assaf Naor của Đại học Princeton. “Một số toán học cũ trở nên phù hợp với khoa học máy tính; khoa học máy tính trả lại và giải quyết câu hỏi bằng toán học. Thật tuyệt khi điều này xảy ra.”

Nhưng hình dạng đó, mặc dù tối ưu, lại thiếu một thứ quan trọng: nền tảng hình học. Bởi vì sự tồn tại của nó đã được chứng minh bằng các kỹ thuật từ khoa học máy tính, hình học thực tế của nó rất khó nắm bắt. Đó là những gì Naor, cùng với Oded Regev, một nhà khoa học máy tính tại Viện Courant thuộc Đại học New York, đã bắt đầu sửa lỗi trong một bằng chứng được đăng trực tuyến vào tháng trước.

“Đó là một kết thúc rất hay cho câu chuyện,” Regev nói.

bọt hình khối

Các nhà toán học đã xem xét các phiên bản khác của bài toán bọt biển — bao gồm cả điều xảy ra nếu bạn chỉ được phép phân vùng không gian theo cái được gọi là mạng số nguyên. Trong phiên bản đó của bài toán, bạn lấy một mảng hình vuông gồm các điểm cách đều nhau (mỗi điểm cách nhau 1 đơn vị) và biến mỗi điểm đó thành tâm của một hình. Bài toán bọt “khối lập phương” hỏi diện tích bề mặt tối thiểu sẽ là bao nhiêu khi bạn được yêu cầu lát không gian theo cách này.

Ban đầu, các nhà nghiên cứu quan tâm đến việc áp đặt hạn chế này để hiểu các tính chất của không gian tô pô gọi là đa tạp. Nhưng câu hỏi đã có một cuộc sống riêng, trở nên phù hợp trong phân tích dữ liệu và các ứng dụng khác.

Nó cũng thú vị về mặt hình học, bởi vì nó thay đổi ý nghĩa của “tối ưu”. Ví dụ, trong hai chiều, các hình lục giác đều không còn có thể xếp trên mặt phẳng nếu chúng chỉ có thể dịch chuyển một lượng nguyên theo hướng ngang và dọc. (Bạn phải di chuyển chúng với số lượng không hợp lý theo một trong hai hướng.)

Hình vuông có thể. Nhưng đó có phải là điều tốt nhất có thể được thực hiện? Là nhà toán học Jaigyoung Choe được phát hiện vào năm 1989, câu trả lời là không. Thay vào đó, hình dạng tối ưu là một hình lục giác được nén theo một hướng và kéo dài theo một hướng khác. (Chu vi của một hình lục giác như vậy xấp xỉ 3.86 khi diện tích của nó là 1 — lớn hơn chu vi hình vuông là 4.)

Những khác biệt này có vẻ tầm thường, nhưng chúng lớn hơn nhiều ở các chiều cao hơn.

Trong số tất cả các hình dạng của một thể tích nhất định, hình có diện tích bề mặt nhỏ nhất là hình cầu. BẰNG n, số chiều, lớn dần, diện tích mặt cầu tăng tỉ lệ với căn bậc hai của n.

Nhưng các hình cầu không thể xếp một khoảng trống mà không để lại các khoảng trống. Mặt khác, một n-dạng lập phương thể tích 1 lon. Điều thú vị là diện tích bề mặt của nó là 2n, phát triển tỷ lệ thuận với kích thước của nó. Một khối lập phương 10,000 chiều của tập 1 có diện tích bề mặt là 20,000 — lớn hơn nhiều so với 400, diện tích bề mặt gần đúng của một hình cầu 10,000 chiều.

Và vì vậy các nhà nghiên cứu tự hỏi liệu họ có thể tìm thấy một “khối hình cầu” - một hình dạng có thể xếp nkhông gian có nhiều chiều, giống như một khối lập phương, nhưng diện tích bề mặt của nó tăng chậm, giống như một khối cầu.

Nó dường như không thể. “Nếu bạn muốn bong bóng của mình lấp đầy chính xác không gian và tập trung vào lưới lập phương này, thật khó để nghĩ xem bạn sẽ sử dụng cái gì ngoại trừ bong bóng lập phương,” nói Ryan O'Donnell, một nhà khoa học máy tính lý thuyết tại Đại học Carnegie Mellon. “Có vẻ như khối lập phương phải là tốt nhất.”

Bây giờ chúng tôi biết rằng nó không phải là.

Độ khó của những vấn đề khó

Trong nhiều thập kỷ, vấn đề bọt lập phương tương đối chưa được khám phá ở các chiều cao hơn. Những nhà nghiên cứu đầu tiên đạt được tiến bộ về nó không đến từ lĩnh vực hình học mà từ khoa học máy tính lý thuyết. Họ tình cờ bắt gặp nó khi đang tìm cách chứng minh một phát biểu trung tâm trong lĩnh vực của họ được gọi là phỏng đoán trò chơi độc đáo. “Phỏng đoán về các trò chơi độc đáo,” Regev nói, “hiện tại tôi xem là câu hỏi mở lớn nhất trong khoa học máy tính lý thuyết.”

Được đề xuất vào năm 2002 bởi Subhash Khot, một sinh viên mới tốt nghiệp vào thời điểm đó, phỏng đoán đặt ra rằng nếu một vấn đề cụ thể — một vấn đề liên quan đến việc gán màu cho các nút của mạng — không thể giải chính xác, thì việc tìm kiếm ngay cả một giải pháp gần đúng cũng rất khó. Nếu đúng, phỏng đoán này sẽ cho phép các nhà nghiên cứu hiểu được mức độ phức tạp của vô số nhiệm vụ tính toán khác trong một lần thực hiện.

Các nhà khoa học máy tính thường phân loại các nhiệm vụ dựa trên việc liệu chúng có thể được giải quyết bằng một thuật toán hiệu quả hay không, hoặc thay vào đó chúng là “NP-hard” (có nghĩa là chúng không thể được giải quyết một cách hiệu quả khi quy mô của vấn đề tăng lên, miễn là nhưng phỏng đoán chưa được chứng minh về độ phức tạp tính toán là đúng). Chẳng hạn, bài toán người bán hàng lưu động, yêu cầu tìm đường ngắn nhất cần thiết để đến mọi thành phố trong mạng chỉ một lần, là NP-khó. Vì vậy, việc xác định xem một biểu đồ — một tập hợp các đỉnh được nối với nhau bằng các cạnh — có thể được dán nhãn bằng nhiều nhất ba màu sao cho bất kỳ hai đỉnh được nối nào có các màu khác nhau hay không.

Nó chỉ ra rằng thật khó để tìm ra một giải pháp gần đúng cho nhiều nhiệm vụ trong số này. Giả sử bạn muốn gắn nhãn các đỉnh của biểu đồ bằng các màu khác nhau theo cách thỏa mãn một số danh sách ràng buộc. Nếu việc đáp ứng tất cả các ràng buộc đó là khó NP, vậy còn việc cố gắng chỉ hoàn thành 90% trong số chúng, hoặc 75% hoặc 50% thì sao? Dưới một số ngưỡng, có thể đưa ra một thuật toán hiệu quả, nhưng trên ngưỡng đó, vấn đề trở thành NP-hard.

Trong nhiều thập kỷ, các nhà khoa học máy tính đã làm việc để xác định ngưỡng cho các vấn đề tối ưu hóa khác nhau được quan tâm. Nhưng một số câu hỏi trốn tránh loại mô tả này. Mặc dù một thuật toán có thể đảm bảo 80% giải pháp tốt nhất, nhưng NP-hard có thể đạt được 95% giải pháp tốt nhất, khiến câu hỏi đặt ra là chính xác từ 80% đến 95% vấn đề nằm ở đâu trong lãnh thổ NP-hard.

Phỏng đoán trò chơi độc đáo, hay UGC, cung cấp một cách để xác định ngay câu trả lời. Nó đưa ra một tuyên bố thoạt đầu có vẻ hạn chế hơn: đó là NP-khó có thể phân biệt được sự khác biệt giữa một biểu đồ mà bạn có thể đáp ứng gần như tất cả một tập hợp các ràng buộc tô màu nhất định (giả sử hơn 99%) và một biểu đồ cho mà bạn hầu như không thể đáp ứng bất kỳ (giả sử, ít hơn 1%).

Nhưng ngay sau khi UGC được đề xuất vào năm 2002, các nhà nghiên cứu đã chỉ ra rằng nếu phỏng đoán là đúng, thì bạn có thể dễ dàng tính ngưỡng độ cứng cho bất kỳ bài toán thỏa mãn ràng buộc nào. (Điều này là do UGC cũng ngụ ý rằng một thuật toán đã biết đạt được giá trị gần đúng tốt nhất có thể cho tất cả các vấn đề này.) “Đó chính xác là mấu chốt cho tất cả các vấn đề tối ưu hóa này,” O'Donnell nói.

Và vì vậy, các nhà khoa học máy tính lý thuyết bắt đầu chứng minh UGC - một nhiệm vụ cuối cùng đã khiến một số người trong số họ khám phá ra các khối hình cầu.

Làm cho những vấn đề khó trở nên khó hơn

Năm 2005, O'Donnell đang làm việc tại Microsoft Research. Ông và hai đồng nghiệp - Uriel Feige, hiện tại Viện Khoa học Weizmann, và anh chàng Kindler, hiện đang làm việc tại Đại học Hebrew ở Jerusalem — đã hợp tác để xử lý UGC.

Họ có một ý tưởng mơ hồ về cách họ muốn tiến hành. Họ sẽ bắt đầu với một câu hỏi về đồ thị — một câu hỏi rất giống với UGC. Cái gọi là bài toán cắt cực đại (“max-cut”), khi cho một đồ thị, yêu cầu làm thế nào để phân chia các đỉnh của nó thành hai tập hợp (hoặc màu sắc) sao cho số cạnh nối các tập hợp đó là lớn nhất có thể. (Bạn có thể coi max cut như một câu hỏi về cách tốt nhất để tô màu một đồ thị bằng hai màu sao cho càng ít cạnh càng tốt nối các đỉnh có cùng màu.)

Nếu UGC là đúng, điều đó có nghĩa là, với một biểu đồ ngẫu nhiên nào đó, thuật toán xấp xỉ hiệu quả chỉ có thể đạt được trong khoảng 87% mức cắt tối đa thực sự của biểu đồ đó. Làm tốt hơn sẽ là NP-hard.

Thay vào đó, Feige, Kindler và O'Donnell muốn đi theo hướng ngược lại: Họ hy vọng chỉ ra rằng khó có thể ước lượng được độ cắt tối đa, và sau đó sử dụng điều đó để chứng minh UGC. Kế hoạch của họ dựa trên sức mạnh của một kỹ thuật gọi là sự lặp lại song song — một chiến lược thông minh khiến những vấn đề khó trở nên khó hơn.

Giả sử bạn biết rằng thật khó để phân biệt giữa vấn đề bạn có thể giải quyết và vấn đề bạn hầu như có thể giải quyết. Sự lặp lại song song cho phép bạn xây dựng dựa trên điều đó để hiển thị kết quả về độ cứng mạnh hơn nhiều: rằng việc phân biệt giữa vấn đề bạn có thể giải quyết và vấn đề bạn hầu như không thể giải quyết được cũng là NP-hard. Naor cho biết: “Hiện tượng sâu sắc, phi trực giác này… nằm trong tâm trí của rất nhiều ngành khoa học máy tính ngày nay.

Nhưng có một nhược điểm. Sự lặp lại song song không phải lúc nào cũng khuếch đại độ khó của vấn đề nhiều như các nhà khoa học máy tính mong muốn. Đặc biệt, có những khía cạnh của vấn đề max-cut “gây đau đầu cho việc lặp lại song song,” Regev nói.

Feige, Kindler và O'Donnell tập trung vào việc chỉ ra rằng sự lặp lại song song có thể hoạt động bất chấp những cơn đau đầu. “Đây là một điều thực sự phức tạp để phân tích,” nói Dana Moshkovitz, một nhà khoa học máy tính lý thuyết tại Đại học Texas, Austin. “Nhưng điều này có vẻ gần như trêu ngươi. Sự lặp lại song song có vẻ như sẽ [giúp tạo ra] mối liên hệ này từ trò chơi bị cắt tối đa thành các trò chơi độc đáo.”

Để khởi động, các nhà nghiên cứu đã cố gắng tìm hiểu sự lặp lại song song cho một trường hợp cắt tối đa đơn giản, cái mà Moshkovitz gọi là “lần cắt tối đa ngu ngốc nhất”. Xét một số lẻ các đỉnh được nối với nhau bằng các cạnh để tạo thành một đường tròn hay còn gọi là “chu trình lẻ”. Bạn muốn gắn nhãn mỗi đỉnh bằng một trong hai màu sao cho không có cặp đỉnh liền kề nào có cùng màu. Trong trường hợp này, điều đó là không thể: Một cạnh sẽ luôn kết nối các đỉnh cùng màu. Bạn phải xóa cạnh đó, “phá vỡ” chu kỳ kỳ lạ, để đồ thị của bạn thỏa mãn ràng buộc của bài toán. Cuối cùng, bạn muốn giảm thiểu tổng số cạnh mà bạn cần xóa để tô màu đúng biểu đồ của mình.

Sự lặp lại song song cho phép bạn xem xét một phiên bản nhiều chiều của vấn đề này - một phiên bản trong đó bạn phải phá vỡ tất cả các chu kỳ kỳ lạ xuất hiện. Feige, Kindler và O'Donnell cần chứng minh rằng khi số lượng kích thước trở nên rất lớn, bạn phải xóa một phần rất lớn các cạnh để phá vỡ tất cả các chu kỳ lẻ. Nếu điều đó là đúng, điều đó có nghĩa là sự lặp lại song song có thể khuếch đại một cách hiệu quả độ khó của bài toán “cắt tối đa ngu ngốc” này.

Đó là lúc nhóm phát hiện ra một sự trùng hợp kỳ lạ: Có một cách hình học để giải thích liệu sự lặp lại song song có hoạt động theo cách họ mong đợi hay không. Bí mật nằm ở diện tích bề mặt của bọt lập phương.

Từ chanh đến nước chanh

Vấn đề của họ, được viết lại bằng ngôn ngữ của bọt, được rút gọn lại để chỉ ra rằng các khối hình cầu không thể tồn tại — rằng không thể phân vùng không gian nhiều chiều dọc theo mạng số nguyên thành các ô có diện tích bề mặt nhỏ hơn nhiều so với diện tích của khối lập phương. (Diện tích bề mặt lớn hơn tương ứng với việc cần phải xóa nhiều cạnh “xấu” hơn trong đồ thị chu kỳ lẻ, như các nhà khoa học máy tính hy vọng sẽ chỉ ra.)

“Chúng tôi giống như, ồ, thật là một vấn đề hình học kỳ lạ, nhưng điều đó có lẽ đúng, phải không?” O'Donnell nói. “Chúng tôi thực sự cần đó là câu trả lời thực sự.” Nhưng ông, Feige và Kindler không chứng minh được điều đó. Vì vậy, vào năm 2007, họ xuất bản một bài báo phác thảo cách họ dự định sử dụng vấn đề này để giúp tấn công UGC.

Chẳng mấy chốc, hy vọng của họ đã tan thành mây khói.

Ran Raz, một nhà khoa học máy tính lý thuyết tại Princeton, người đã chứng minh một số kết quả chính về sự lặp lại song song, đã bị thu hút bởi bài báo của họ. Ông quyết định phân tích sự lặp lại song song cho bài toán chu trình lẻ, một phần là do mối liên hệ với hình học mà Feige, Kindler và O'Donnell đã phát hiện ra.

Raz không bắt đầu với vấn đề bọt mà tấn công trực diện vào phiên bản khoa học máy tính của câu hỏi. Anh ấy đã chỉ ra rằng bạn có thể thoát khỏi việc xóa ít cạnh hơn rất nhiều để phá vỡ tất cả các chu kỳ kỳ lạ trong biểu đồ. Nói cách khác, sự lặp lại song song không thể khuếch đại đủ độ khó của vấn đề cắt tối đa này. Moshkovitz nói: “Các thông số mà người ta nhận được từ sự lặp lại song song chính xác, hoàn toàn không đạt được điều này.

“Kế hoạch của chúng tôi sử dụng sự lặp lại song song để thể hiện độ khó của các trò chơi độc đáo thậm chí không hoạt động trong trường hợp đơn giản nhất,” O'Donnell nói. "Loại này phá vỡ toàn bộ kế hoạch."

Mặc dù đáng thất vọng nhưng kết quả của Raz cũng gợi ý về sự tồn tại của khối cầu: hình khối có khả năng ốp lát nkhông gian -chiều với diện tích bề mặt tỷ lệ với căn bậc hai của n. “Chúng tôi giống như, ồ, chúng ta hãy pha nước chanh từ những quả chanh và lấy kết quả kỹ thuật đáng thất vọng này về sự lặp lại song song và các đồ thị rời rạc, rồi biến nó thành một kết quả gọn gàng, thú vị trong hình học,” O'Donnell nói.

Ông và Kindler, cộng tác với các nhà khoa học máy tính Anup Rao và Avi Wigderson, nghiền ngẫm chứng minh của Raz cho đến khi họ học đủ kỹ thuật của nó để chuyển chúng sang bài toán bọt. Năm 2008, họ đã chứng minh rằng khối hình cầu thực sự có thể.

“Đó là một cách hay để suy luận về vấn đề,” nói đánh dấu dũng cảm của Princeton. "Nó thật đẹp."

Và nó đặt ra câu hỏi về khía cạnh hình học của câu chuyện. Bởi vì họ đã sử dụng công trình của Raz về sự lặp lại song song để xây dựng hình dạng lát gạch của mình, Kindler, O'Donnell, Rao và Wigderson đã kết thúc với một thứ gì đó xấu xí và giống Frankenstein. Gạch lộn xộn và đầy vết lõm. Về mặt toán học, nó không lồi. Mặc dù điều này phù hợp với mục đích của họ, nhưng khối hình cầu thiếu các đặc tính mà các nhà toán học ưa thích — các đặc tính giúp hình dạng trở nên cụ thể hơn, dễ xác định và nghiên cứu hơn, đồng thời phù hợp hơn cho các ứng dụng tiềm năng.

“Có điều gì đó rất không hài lòng về cách xây dựng của họ,” Regev nói. “Nó trông giống như một con amip. Nó không giống như những gì bạn mong đợi, một cơ thể lát gạch đẹp.”

Đó là những gì anh ấy và Naor bắt đầu tìm kiếm.

Thoát khỏi lồng

Ngay từ đầu, Naor và Regev đã nhận ra rằng họ phải bắt đầu lại từ đầu. “Một phần vì các vật thể lồi rất hạn chế nên không có kỹ thuật nào trước đây có cơ hội hoạt động,” cho biết Dor Minzer, một nhà khoa học máy tính lý thuyết tại Viện Công nghệ Massachusetts.

Trên thực tế, hoàn toàn có thể tin rằng tính lồi sẽ quá hạn chế - rằng một khối cầu lồi đơn giản là không tồn tại.

Nhưng tháng trước, Naor và Regev đã chứng minh rằng bạn có thể phân vùng nkhông gian -chiều dọc theo tọa độ nguyên với hình dạng lồi có diện tích bề mặt khá gần với diện tích của hình cầu. Và họ đã làm điều đó hoàn toàn về mặt hình học - đưa vấn đề trở về cội nguồn toán học của nó.

Đầu tiên họ phải vượt qua một trở ngại lớn. Bài toán bọt lập phương yêu cầu mỗi viên gạch được căn giữa tại các tọa độ nguyên. Nhưng trong mạng số nguyên, có những khoảng cách rất ngắn giữa một số điểm — và những khoảng cách ngắn đó gây ra rắc rối.

Xét một điểm trong lưới hai chiều. Nó nằm cách các điểm gần nhất 1 đơn vị theo hướng ngang và dọc. Nhưng theo hướng đường chéo, điểm gần nhất cách xa $latex sqrt{2}$ đơn vị — sự khác biệt sẽ trở nên tồi tệ hơn trong không gian lớn hơn. bên trong n-mạng số nguyên chiều, các điểm gần nhất vẫn cách 1 đơn vị, nhưng các điểm “đường chéo” đó hiện cách xa $latex sqrt{n}$ đơn vị. Ví dụ, trong 10,000 chiều, điều này có nghĩa là điểm lân cận “đường chéo” gần nhất với bất kỳ điểm nào cách xa 100 đơn vị mặc dù có 10,000 điểm khác (mỗi điểm theo một hướng) chỉ cách 1 đơn vị.

Trong các mạng khác, hai loại khoảng cách đó tăng tỷ lệ thuận với nhau. Trong nhiều thập kỷ, các nhà toán học đã biết cách sắp xếp các mạng như vậy với các hình dạng lồi có diện tích bề mặt tối thiểu.

Nhưng trong mạng số nguyên, khoảng cách ngắn nhất sẽ luôn bị kẹt ở mức 1. Điều này cản trở việc xây dựng một ô đẹp mắt có diện tích bề mặt tối ưu. Regev nói: “Họ đã nhốt bạn vào cái lồng này. "Họ làm cho mọi thứ rất chặt chẽ xung quanh bạn."

Vì vậy, thay vào đó, Naor và Regev được coi là một phần của toàn bộ n-chiều không gian. Họ cẩn thận chọn không gian con này để nó vẫn có nhiều điểm nguyên, nhưng không có điểm nào quá gần nhau.

Nói cách khác, không gian con mà họ đạt được chính xác là loại mà các nhà toán học đã biết cách sắp xếp một cách tối ưu.

Nhưng đây mới chỉ là một nửa công việc. Naor và Regev cần phân vùng toàn bộ không gian, không chỉ một phần của nó. Để có được một n-khối hình cầu hai chiều, họ phải nhân ô hiệu quả của mình với một ô từ không gian còn lại (tương tự như cách bạn có thể nhân một hình vuông hai chiều với một đoạn thẳng một chiều để có được một hình khối ba chiều). Làm như vậy sẽ nâng công trình của họ trở lại không gian ban đầu, nhưng nó cũng sẽ làm tăng diện tích bề mặt của nó.

Cặp đôi phải chỉ ra rằng gạch từ không gian còn lại, không tối ưu, không thêm quá nhiều vào diện tích bề mặt. Một khi họ đã làm điều đó, việc xây dựng của họ đã hoàn tất. (Diện tích bề mặt của hình dạng cuối cùng của họ cuối cùng lớn hơn một chút so với diện tích bề mặt của hình lập phương hình cầu không lồi, nhưng họ tin rằng có thể tìm thấy một viên gạch lồi cũng hiệu quả như đối tác không lồi của nó.)

Nhà toán học cho biết: “Chứng minh của họ hoàn toàn khác” so với công trình trước đây về khối cầu. Noga Alon. “Và khi nhìn lại, đó có thể là một bằng chứng tự nhiên hơn. Đây là điều mà lẽ ra ai đó nên cố gắng bắt đầu.”

“Khi mọi thứ được thực hiện khác đi,” Raz nói thêm, “đôi khi bạn sẽ tìm thấy những hàm ý bổ sung thú vị.”

hy vọng nhen nhóm

Vẫn chưa rõ những ý nghĩa đó có thể là gì - mặc dù công việc khai thác khả năng sử dụng các mạng số nguyên trong mật mã và các ứng dụng khác. Dựa vào mức độ liên quan của vấn đề này với các lĩnh vực khác, “nó có khả năng dẫn đến những thứ khác,” Alon nói.

Hiện tại, các nhà khoa học máy tính không tìm ra cách giải thích kết quả lồi bằng ngôn ngữ lặp lại song song và UGC. Nhưng họ vẫn chưa hoàn toàn từ bỏ kế hoạch ban đầu là sử dụng bài toán bọt để chứng minh phỏng đoán. Kindler nói: “Có nhiều cách khác nhau mà bạn có thể cố gắng phá bỏ những rào cản rõ ràng mà chúng tôi gặp phải.

Braverman và Minzer đã thử một cách như vậy khi họ xem xét lại bọt vào năm 2020. Thay vì yêu cầu hình dạng lát gạch phải lồi, họ yêu cầu nó tuân theo các đối xứng nhất định để nó trông giống nhau cho dù bạn lật tọa độ của nó như thế nào. (Ở dạng 2D, hình vuông sẽ hoạt động, nhưng hình chữ nhật thì không; khối hình cầu nhiều chiều được mô tả cho đến nay cũng vậy.) Dưới sự ràng buộc mới này, cặp đôi đã có thể hiển thị những gì Kindler và những người khác đã hy vọng 15 năm trước: rằng bạn không thể làm tốt hơn nhiều so với diện tích bề mặt của khối lập phương.

Điều này tương ứng với một loại lặp lại song song khác - một loại sẽ làm cho trường hợp cắt tối đa đơn giản nhất trở nên khó khăn nhất có thể. Mặc dù kết quả mang lại một số hy vọng cho hướng nghiên cứu này, nhưng vẫn chưa rõ liệu phiên bản lặp lại song song này có hoạt động đối với tất cả các bài toán max-cut hay không. “Điều đó không có nghĩa là bạn đã hoàn thành,” Braverman nói. “Điều đó chỉ có nghĩa là bạn đã quay trở lại công việc kinh doanh.”

“Có rất nhiều tiềm năng trong hình học,” Minzer nói. “Chỉ là chúng ta hiểu chưa đủ thôi.”