Các nhà khoa học máy tính tiến gần hơn đến mục tiêu thuật toán chính | Tạp chí lượng tử

Nếu ai đó yêu cầu bạn xác định xem hai đối tượng có giống nhau hay không, thì đó có vẻ là một yêu cầu tầm thường. Trong hầu hết các trường hợp hàng ngày, nhìn lướt qua là đủ để bạn đưa ra phán đoán chính xác.

Nhưng trong khoa học máy tính, đó là một câu hỏi phức tạp hơn nhiều. Trên thực tế, đó là một trong những vấn đề cốt lõi chưa được giải đáp về khả năng của máy tính. Tùy thuộc vào đối tượng là gì và cách bạn xác định tính giống nhau, chúng tôi vẫn không biết liệu máy tính có thể trả lời câu hỏi một cách nhanh chóng hay liệu cách tiếp cận chậm và tốn nhiều công sức về cơ bản là cách tốt nhất mà chúng có thể quản lý.

Trong thập kỷ qua, đã có một số kết quả quan trọng chứng minh rằng máy tính có thể làm tốt hơn thế ít nhất một chút. Một trong những kết quả lớn nhất gần đây trong khoa học máy tính là một thuật toán nhanh hơn để xác định khi nào hai biểu đồ giống nhau. Tác phẩm năm 2015 của László Babai của Đại học Chicago, đã phá vỡ một rào cản quan trọng về tốc độ tính toán nhưng lại thiếu một rào cản khác.

Bây giờ, một bài báo của Tiêu Duệ Tôn của Đại học Illinois, Chicago đã trình bày một thuật toán mới, nhanh hơn cho một câu hỏi liên quan được gọi là bài toán đẳng cấu nhóm, đó là về việc biết khi nào hai đối tượng toán học được gọi là nhóm giống nhau. Tác phẩm được đưa lên mạng tháng ba vừa qua, thực hiện một bước nhỏ để làm rõ độ phức tạp tính toán cơ bản liên quan đến việc so sánh các đối tượng.

Công trình của Sun đã phá vỡ giới hạn tốc độ đã có từ lâu đối với một loại nhóm cụ thể — giới hạn được coi là trường hợp khó giải quyết nhất của bài toán đẳng cấu nhóm. Nếu một thuật toán có thể nhanh chóng so sánh các nhóm thuộc loại này, thì hy vọng là nó có thể nhanh chóng so sánh các nhóm thuộc bất kỳ loại nào.

“Chúng tôi không biết một định lý như vậy, nhưng chúng tôi có lý do để tin rằng điều gì đó như thế là đúng,” ông nói Josh Grochow của Đại học Colorado, Boulder.

So sánh So sánh

Để xác định xem hai thứ có giống nhau một cách chính xác hay không, trước tiên bạn cần định nghĩa “giống nhau”. Hai chuỗi số có thể được coi là giống nhau nếu chúng chỉ chứa các chữ số giống nhau hoặc chúng có thể cần phải có các chữ số giống nhau theo cùng một thứ tự.

Đẳng cấu là một loại giống nhau đặc biệt xuất hiện rất nhiều trong toán học. Khi hai đối tượng đẳng cấu với nhau, điều đó có nghĩa là chúng chứa các phần tử giống nhau và các phần tử đó có cùng mối quan hệ với nhau.

Đồ thị — tập hợp các đỉnh (chấm) được liên kết bởi các cạnh (đường) — cung cấp một cách trực quan, dễ tiếp cận để xem đẳng cấu có thể trông như thế nào. Hai đồ thị là đẳng cấu nếu bạn có thể nối các đỉnh của đồ thị này với các đỉnh của đồ thị kia, sao cho các đỉnh được nối với nhau bằng một cạnh trong đồ thị thứ nhất được nối với một cạnh trong đồ thị thứ hai. Các đồ thị đẳng cấu có thể trông khác nhau trên bề mặt, nhưng chúng có chung một cấu trúc cơ bản.

Các nhóm trừu tượng hơn đồ thị, nhưng chúng vẫn có thể so sánh được bằng đẳng cấu. Một nhóm là một tập hợp các phần tử—chẳng hạn như các số—có thể được kết hợp với nhau theo một số thao tác để kết quả cũng nằm trong tập hợp. Ví dụ: bạn có thể có một nhóm có các phần tử là số nguyên — tất cả các số nguyên âm và dương, cộng với số XNUMX — và phép toán của nhóm là phép cộng: Cộng hai số nguyên bất kỳ và kết quả luôn là một số nguyên khác.

Hai nhóm là đẳng cấu nếu bạn có thể ghép từng phần tử trong một nhóm với một phần tử trong nhóm kia, sao cho kết quả của phép toán trên hai phần tử trong nhóm thứ nhất nhất quán với kết quả của phép toán trên các giá trị tương đương của các phần tử đó trong nhóm thứ hai nhóm.

Đây là một ví dụ đơn giản về hai nhóm, mỗi nhóm có hai phần tử, đẳng cấu với nhau. Nhóm đầu tiên bao gồm các số 0 và 1, và nhóm thứ hai bao gồm các chữ cái a và b. Cả hai nhóm đều chứa một thao tác để kết hợp các phần tử của nhóm theo một cách cụ thể, với kết quả được trình bày trong các bảng bên dưới.

Các nhóm đẳng cấu vì 0 cặp với a, 1 cặp với bvà mối quan hệ cấu trúc được tạo ra bằng cách kết hợp các phần tử là giống nhau ở cả hai nhóm.

“Chúng tôi nói rằng hai nhóm là đẳng cấu nếu về cơ bản chúng tương đương nhau,” Sun nói.

Tiến trình không cân bằng

Đẳng cấu là một khái niệm quan trọng trong toán học — trong đó biểu đồ và nhóm được sử dụng rộng rãi — bởi vì nó cho phép các nhà toán học bỏ qua những khác biệt bề ngoài và tập trung vào cách thức mà các đối tượng liên quan có thể thực sự giống nhau. Nhưng nó cũng là nền tảng trong khoa học máy tính; các nhà nghiên cứu không chỉ tìm kiếm các thuật toán xác định xem hai đối tượng có đẳng cấu hay không mà còn đo lường tốc độ chạy của các thuật toán đó.

Phép đo đó có thể phức tạp. Tốc độ của một thuật toán dựa trên cách thời gian chạy của nó thay đổi theo kích thước của các đối tượng mà nó đang làm việc. Ví dụ, hãy tưởng tượng rằng bạn có hai cặp nhóm. Trong một cặp, mỗi nhóm chứa năm yếu tố. Mặt khác, mỗi nhóm chứa 10 phần tử.

Bạn cho rằng thuật toán sẽ mất nhiều thời gian hơn để xác định xem các nhóm có nhiều phần tử hơn có phải là đẳng cấu hay không. Nhưng còn bao nhiêu thời gian nữa? Sẽ mất gấp đôi thời gian? 5² lâu hơn? 2⁵ lâu hơn? Những câu hỏi đó tương ứng với các phân loại quan trọng về tốc độ thuật toán: Chúng có thể chạy trong thời gian tuyến tính (có nghĩa là trong trường hợp này mất gấp đôi thời gian), thời gian đa thức (5² lâu hơn) và thời gian theo cấp số nhân (2⁵ lâu hơn).

Các nhà khoa học máy tính biết hầu hết các câu hỏi về máy tính thuộc loại tốc độ nào, nhưng không phải tất cả.

“Hầu hết đều là [loại câu hỏi] dễ nhất hoặc khó nhất, nhưng vẫn có một số trường hợp ngoại lệ chưa được biết,” Sun nói. Đẳng cấu đồ thị và nhóm nằm trong số những trường hợp ngoại lệ đó, đó là điều khiến chúng trở nên hấp dẫn để nghiên cứu.

Trong 1970s, Robert Tarjan của Đại học Princeton nhận ra rằng có một thuật toán có thể xác định xem hai nhóm bất kỳ có đẳng cấu hay không với thời gian chạy là $latex n^{{(log,n)}}$, trong đó n là số phần tử trong mỗi nhóm. Đây được gọi là thuật toán thời gian bán đa thức và trong hệ thống phân cấp thời gian chạy, thuật toán này tốt hơn thời gian hàm mũ (2ⁿ) nhưng tệ hơn thời gian đa thức (n²). Tốc độ này xấp xỉ bằng tốc độ của thuật toán đẳng cấu đồ thị của Babai và đó vẫn là tốc độ tốt nhất chúng ta có thể làm cho các nhóm gần 50 năm sau.

“Điều đó có nghĩa là không có tiến triển nào trong nửa thế kỷ,” Sun nói.

Vào thời điểm kết quả của Tarjan, bài toán đẳng cấu nhóm được nghiên cứu rộng rãi hơn phiên bản đồ thị. Ngày nay, điều đó đã bị đảo lộn, một phần là do đẳng cấu đồ thị đã thúc đẩy những đổi mới thú vị trong khi đẳng cấu nhóm đã bị đình trệ.

“Tất cả các công cụ của chúng tôi đã rất chậm trong nhiều năm và thật khó để khai thác những gì chúng tôi biết về đại số [của các nhóm],” cho biết James Wilson của Đại học Bang Colorado.

Nhưng bất chấp sự chênh lệch về tiến trình này, hai vấn đề có mối liên hệ sâu sắc hơn so với sự giống nhau về tên gọi của chúng: Vấn đề đẳng cấu nhóm (ít nhất là trong công thức này) quy về vấn đề đẳng cấu đồ thị. Điều này có nghĩa là bất kỳ thuật toán nào có thể giải bài toán đồ thị cũng có thể giải bài toán nhóm trong một khoảng thời gian tương tự. Điều ngược lại là không đúng — tiến trình trên nhóm không có nghĩa là tiến triển trên biểu đồ. Nhưng việc thiếu những tiến bộ trong bài toán nhóm đã đè nặng lên các nhà toán học đang tìm kiếm những lợi ích tương xứng trong bài toán đồ thị. Làm sao bạn có thể hoàn thành một việc khó khăn hơn nếu trước tiên bạn không thể hoàn thành một việc gì đó có liên quan chặt chẽ và dường như còn dễ dàng hơn?

“Nói cách khác,” Sun nói, “để cải thiện hơn nữa đẳng cấu đồ thị, đẳng cấu nhóm là một nút cổ chai lớn.”

Một vấn đề được chuyển đổi

Khi tiến trình giải quyết một vấn đề bị đình trệ chừng nào nó đã xảy ra đối với đẳng cấu nhóm, thì thường cần phải phát minh ra để giải quyết vấn đề đó. Grochow nói: “Khi bạn có một bước tiến lớn, đó sẽ là dấu hiệu cho thấy có một ý tưởng mới.

Công việc của Sun bao gồm một vài ý tưởng liên quan đến việc nhắm mục tiêu vào một loại nhóm quan trọng và tìm ra một cách thông minh để chia các nhóm đó thành nhiều phần để so sánh chúng.

Các nhóm mà thuật toán của Sun hoạt động được gọi là p-nhóm hạng 2 và số mũ p. Chúng tương tự như các nhóm trong đó tích của hai phần tử là một phần tử khác và tích không đổi bất kể bạn nhân chúng theo thứ tự nào. Nhưng điều thực sự quan trọng là những gì chúng đại diện cho bài toán đẳng cấu nhóm tổng thể. Các nhóm này có cấu trúc rất đơn giản, có nghĩa là chúng sẽ dễ so sánh. Nhưng bất chấp sự đơn giản này, các nhà nghiên cứu vẫn chưa tìm ra cách tăng tốc thuật toán. Cho đến khi họ có thể, thật vô vọng để cải thiện câu hỏi chung về đẳng cấu nhóm.

Sun bắt đầu bằng cách chuyển cài đặt từ nhóm sang ma trận, mảng số đóng vai trò là đối tượng nền tảng trong đại số tuyến tính. Điều này có thể là do một định lý từ những năm 1930 gọi là tương ứng Baer, ​​biến phiên bản này của câu hỏi đẳng cấu nhóm thành một bài toán hoàn toàn tương tự về ma trận. Cụ thể, Sun đã làm việc với không gian ma trận, là tập hợp các ma trận có thuộc tính đặc biệt: Tổ hợp (tuyến tính) của hai ma trận bất kỳ trong không gian bằng một ma trận khác trong không gian.

Nói cách khác, những không gian này được cấu trúc giống như các nhóm. Vì vậy, thay vì cố gắng hiểu khi nào hai nhóm là đẳng cấu, Sun chỉ có thể cố gắng hiểu khi nào hai không gian ma trận là đẳng cự — một khái niệm về đẳng cấu của không gian ma trận tương ứng với không gian của các nhóm.

Sun không phải là nhà nghiên cứu đầu tiên áp dụng cách tiếp cận này, nhưng ông là người đầu tiên giới thiệu một bước bổ sung: chia không gian ma trận thành hai phần. Một mảnh là cốt lõi của không gian, trong đó tất cả các ma trận đều đơn giản. Phần còn lại là không gian xung quanh lõi đó, trong đó tất cả các ma trận đều đặc biệt phức tạp. Động thái này tương ứng với việc tách một nhóm thành các nhóm con chỉ chứa một số phần tử trong tổng số.

Sun sau đó đã áp dụng các phương pháp thuật toán khác nhau cho từng phần này. Lõi có cấu trúc đơn giản, vì vậy ông đã sử dụng đặc tính của cấu trúc để thể hiện nó theo cách có tổ chức hơn. Lớp bên ngoài phức tạp hơn, vì vậy rõ ràng không có cách nào nhanh chóng để so sánh nó với lớp khác. Thay vào đó, phương pháp của Sun sử dụng một cách tiếp cận được gọi là cá thể hóa và sàng lọc để loại trừ hầu hết các cách khả thi để ánh xạ một lớp bên ngoài lên lớp kia và sau đó sử dụng máy tính để xử lý tất cả các cách khả thi còn lại để xác định xem có tồn tại sự khớp đẳng cấu hay không.

Về tinh thần, phương pháp này tương tự như cách bạn có thể giải một câu đố sudoku. Có một số ô vuông có giá trị tiềm năng bị hạn chế bởi những gì bạn đã biết (lõi của không gian ma trận), cho phép bạn điền vào chúng một cách nhanh chóng. Sau đó, có những lớp khác (lớp bên ngoài) có ít ràng buộc hơn, nhưng bạn có thể tìm ra chỉ bằng cách thử tất cả các giá trị có thể — và miễn là không có quá nhiều loại ô vuông này, bạn vẫn có thể giải câu đố trong một khoảng thời gian hợp lý.

Wilson nói: “Tôi điền vào tất cả những thứ mà tôi có thể nhanh chóng nhận ra là có thể hạn chế được, và bây giờ tôi có thể quay lại và thử hết sức mình với những ô còn thiếu. “Nếu bạn đã thu hẹp phạm vi, bây giờ là thời điểm tốt để chuyển sang số và sử dụng máy tính để tìm kiếm các giá trị phù hợp.”

Bước đột phá của Sun đã chỉ ra rằng luôn luôn có thể thực hiện phép chia này cho các không gian ma trận tương ứng với p-nhóm hạng 2 và số mũ p. Sau đó, ông đã chứng minh rằng sau khi phân tách như vậy, sự kết hợp của các kỹ thuật thuật toán giúp xác định xem hai không gian có đẳng cấu hay không trong $latex n^{{(log,n)}^{5/6}}$ thời gian, một giá trị là thấp hơn một chút so với phương thức $latex n^{{(log,n)}}$ của Tarjan. (Cả hai thuật toán cũng bao gồm các thuật ngữ không đổi, không có ảnh hưởng lớn đến thời gian chạy và chúng tôi đã loại bỏ điều này cho rõ ràng.)

Kết quả không xác định đẳng cấu nhóm loại tốc độ nào rơi vào; nó vẫn ở đâu đó giữa thời gian hàm mũ và đa thức. Nhưng Sun đã đẩy nó gần hơn một chút về khía cạnh đa thức của sự vật, và có lý do để tin rằng nhiều hơn thế là có thể. Xét cho cùng, công trình của ông cung cấp cho các nhà khoa học máy tính một thuật toán đẳng cấu nhóm nhanh hơn cho các loại nhóm khó khăn nhất, nâng cao khả năng rằng một sự tăng tốc tương tự có thể nằm trong tầm với của các loại nhóm.

“Nếu bạn có thể giải quyết nó cho p-nhóm, có lẽ bạn có thể giải quyết toàn bộ,” Grochow nói. "Có lẽ."