Con số 15 mô tả giới hạn bí mật của lưới vô hạn

Là một sinh viên đại học tại Đại học Chile, Bernardo Subercaseaux coi thường việc sử dụng máy tính để làm toán. Nó dường như trái ngược với khám phá trí tuệ thực sự.

Ông nói: “Có một số bản năng hoặc phản ứng ruột thịt chống lại việc sử dụng máy tính để giải quyết vấn đề của bạn, giống như nó đi ngược lại vẻ đẹp lý tưởng hoặc sự tao nhã của một lập luận tuyệt vời.

Nhưng sau đó vào năm 2020, Subercaseaux đã yêu và như thường lệ, các ưu tiên của anh ấy đã thay đổi. Đối tượng ám ảnh của anh ấy là một câu hỏi anh ấy nhìn thấy trên một diễn đàn trực tuyến. Hầu hết các vấn đề anh ấy xem qua và quên mất, nhưng vấn đề này khiến anh ấy chú ý. Anh vuốt sang phải.

“Điều đầu tiên tôi làm là thích bài đăng trong nhóm Facebook, hy vọng sẽ nhận được thông báo sau khi ai đó đăng giải pháp,” anh nói.

Câu hỏi là về việc lấp đầy một lưới vô hạn bằng các con số. Hóa ra đó không phải là loại vấn đề mà người ta giải quyết một cách nhanh chóng. Để làm được điều đó, Subercaseaux phải rời Chile để học cao học tại Đại học Carnegie Mellon.

Ở đó, vào tháng 2021 năm XNUMX, anh ấy đã có một cuộc gặp gỡ tình cờ với Marijn Heule, một nhà khoa học máy tính sử dụng sức mạnh tính toán khổng lồ để giải các câu hỏi toán khó. Subercaseaux đã hỏi Heule liệu anh ấy có muốn thử giải bài toán này hay không, bắt đầu một sự hợp tác lên đến đỉnh điểm vào tháng Giêng năm nay. một bằng chứng có thể được tóm tắt bằng một số duy nhất: 15.

mọi cách có thể

Trong 2002, Wayne Goddard của Đại học Clemson và một số nhà toán học có cùng chí hướng đang giải quyết các vấn đề về tổ hợp, cố gắng tìm ra những điểm mới cho các câu hỏi cơ bản của lĩnh vực này về bản đồ tô màu với những hạn chế nhất định.

Cuối cùng, họ gặp phải một vấn đề bắt đầu bằng một ô vuông, giống như một tờ giấy vẽ đồ thị kéo dài mãi mãi. Mục tiêu là để lấp đầy nó với các con số. Chỉ có một ràng buộc: Khoảng cách giữa mỗi lần xuất hiện của cùng một số phải lớn hơn chính số đó. (Khoảng cách được đo bằng cách cộng khoảng cách theo chiều dọc và chiều ngang, một số liệu được gọi là khoảng cách “taxi” cho cách nó giống như di chuyển trên đường đô thị có kẻ ô.) Một cặp số 1 không thể chiếm các ô liền kề, có khoảng cách taxi là 1, nhưng chúng có thể được đặt trong các ô có đường chéo trực tiếp, có khoảng cách là 2.

Ban đầu, Goddard và các cộng tác viên của ông muốn biết liệu có thể lấp đầy một lưới vô hạn bằng một tập hợp các số hữu hạn hay không. Nhưng vào thời điểm anh ta và bốn cộng tác viên của mình đã xuất bản vấn đề "tô màu bao bì" này trên tạp chí Tổ hợp Ars vào năm 2008, họ đã chứng minh rằng nó có thể được giải bằng 22 số. Họ cũng biết rằng không thể nào giải được chỉ với năm con số. Điều đó có nghĩa là câu trả lời thực sự cho vấn đề - số lượng tối thiểu cần thiết - nằm ở đâu đó ở giữa.

Các nhà nghiên cứu đã không thực sự lấp đầy một mạng lưới vô hạn. Họ không cần phải làm vậy. Thay vào đó, chỉ cần lấy một tập hợp con nhỏ của lưới — chẳng hạn như một hình vuông 10 x 10 — điền vào ô đó bằng các số, sau đó cho thấy rằng các bản sao của tập hợp con đã điền có thể được đặt cạnh nhau, theo cách bạn che một ô sàn với các bản sao của gạch.

Khi Subercaseaux lần đầu tiên biết về vấn đề này, anh ấy bắt đầu tìm kiếm các viên gạch bằng bút và giấy. Anh ấy sẽ phác thảo các ô số, gạch bỏ chúng, thử lại. Anh ấy nhanh chóng cảm thấy mệt mỏi với cách tiếp cận đó và anh ấy đã nhờ một người bạn thiết kế một công cụ dựa trên web giống với trò chơi Minesweeper và cho phép anh ấy thử nghiệm các kết hợp nhanh hơn. Sau vài tuần làm việc nữa, anh ấy đã tự thuyết phục mình rằng không có cách nào để đóng gói một ô có tám số, nhưng anh ấy không thể tiến xa hơn thế nữa - có quá nhiều hình dạng tiềm năng mà các ô có thể có, và quá nhiều những cách khác nhau mà chúng có thể được điền bằng các con số.

Vấn đề, như sau này sẽ trở nên rõ ràng, là rất khó để chỉ ra rằng lưới không thể được bao phủ bởi một tập hợp số nhất định hơn là chỉ ra rằng nó có thể. Goddard nói: “Nó không chỉ cho thấy rằng một cách không hiệu quả, mà còn cho thấy rằng mọi cách có thể đều không hiệu quả.

Sau khi Subercaseaux bắt đầu làm việc tại CMU và thuyết phục Heule làm việc với mình, họ nhanh chóng tìm ra cách bao phủ lưới với 15 con số. Họ cũng có thể loại trừ khả năng giải bài toán chỉ với 12 con số. Nhưng cảm giác chiến thắng của họ chỉ tồn tại trong thời gian ngắn khi họ nhận ra rằng họ chỉ sao chép lại những kết quả đã có từ lâu: Từ năm 2017, các nhà nghiên cứu đã biết câu trả lời không nhỏ hơn 13 hoặc lớn hơn 15 .

Đối với một sinh viên tốt nghiệp năm thứ nhất, người đã thuyết phục được một giáo sư nổi tiếng tham gia giải quyết vấn đề thú cưng của mình, đó là một khám phá đáng lo ngại. “Tôi đã rất kinh hoàng. Về cơ bản, tôi đã nghiên cứu một vấn đề trong vài tháng mà không nhận ra điều này, và tệ hơn nữa, tôi đã khiến Marijn lãng phí thời gian của mình vào nó!” Subercaseaux đã viết trong một bài đăng trên blog tóm tắt lại công việc của họ.

Tuy nhiên, Heule nhận thấy việc phát hiện ra các kết quả trong quá khứ đã tiếp thêm sinh lực. Nó chứng minh rằng các nhà nghiên cứu khác nhận thấy vấn đề đủ quan trọng để tiếp tục và xác nhận với ông rằng kết quả duy nhất đáng đạt được là giải quyết vấn đề một cách triệt để.

Ông nói: “Khi chúng tôi nhận ra rằng đã có 20 năm nghiên cứu về vấn đề này, điều đó đã thay đổi hoàn toàn bức tranh.

Tránh thô tục

Qua nhiều năm, Heule đã thành công nhờ tìm ra những cách hiệu quả để tìm kiếm trong vô số các kết hợp có thể có. Cách tiếp cận của anh ấy được gọi là giải SAT - viết tắt của “sự hài lòng”. Nó liên quan đến việc xây dựng một công thức dài, được gọi là công thức Boolean, có thể có hai kết quả: 0 hoặc 1. Nếu kết quả là 1, công thức là đúng và vấn đề được thỏa mãn.

Đối với bài toán tô màu đóng gói, mỗi biến trong công thức có thể biểu thị liệu một ô đã cho có bị chiếm bởi một số đã cho hay không. Máy tính tìm cách gán các biến để thỏa mãn công thức. Nếu máy tính có thể làm điều đó, bạn biết rằng có thể đóng gói lưới theo các điều kiện bạn đã đặt.

Thật không may, một mã hóa đơn giản của vấn đề tô màu đóng gói dưới dạng công thức Boolean có thể kéo dài đến hàng triệu thuật ngữ - một máy tính hoặc thậm chí một nhóm máy tính có thể chạy thử nghiệm mãi mãi tất cả các cách gán biến khác nhau bên trong nó.

Goddard nói: “Cố gắng thực hiện hành động vũ phu này sẽ khiến vũ trụ kết thúc nếu bạn làm điều đó một cách ngây thơ. “Vì vậy, bạn cần một số đơn giản hóa tuyệt vời để đưa nó xuống một thứ thậm chí có thể.”

Hơn nữa, mỗi khi bạn thêm một số vào bài toán tô màu bao bì, nó sẽ khó hơn khoảng 100 lần, do cách thức kết hợp có thể nhân lên. Điều này có nghĩa là nếu một dãy máy tính hoạt động song song có thể loại trừ 12 trong một ngày tính toán, thì chúng sẽ cần thời gian tính toán 100 ngày để loại trừ 13.

Theo một cách nào đó, Heule và Subercaseaux coi việc nhân rộng một cách tiếp cận tính toán mạnh mẽ là thô tục. Subercaseaux cho biết: “Chúng tôi đã có một số ý tưởng đầy hứa hẹn, vì vậy chúng tôi đã có suy nghĩ là 'Hãy cố gắng tối ưu hóa cách tiếp cận của chúng tôi cho đến khi chúng tôi có thể giải quyết vấn đề này trong vòng chưa đầy 48 giờ tính toán trên cụm',” Subercaseaux nói.

Để làm được điều đó, họ phải nghĩ ra các cách hạn chế số lượng kết hợp mà cụm máy tính phải thử.

“[Họ] không chỉ muốn giải quyết mà còn muốn giải quyết nó theo một cách ấn tượng,” ông nói Alexander Soifer của Đại học Colorado, Colorado Springs.

Heule và Subercaseaux đã nhận ra rằng nhiều sự kết hợp về cơ bản là giống nhau. Nếu bạn đang cố gắng lấp đầy một ô hình thoi bằng tám số khác nhau, thì không thành vấn đề nếu số đầu tiên bạn đặt là một ở trên và một ở bên phải của hình vuông ở giữa, hoặc một ở dưới và một ở bên trái của ô vuông trung tâm. quảng trường trung tâm. Hai vị trí đối xứng với nhau và hạn chế nước đi tiếp theo của bạn theo cùng một cách, vì vậy không có lý do gì để kiểm tra cả hai.

Heule và Subercaseaux đã thêm các quy tắc cho phép máy tính coi các kết hợp đối xứng là tương đương nhau, giảm tổng thời gian tìm kiếm xuống 3 lần. Họ cũng sử dụng một kỹ thuật mà Heule đã phát triển trong công việc trước đó có tên là khối lập phương và chinh phục, cho phép họ thử nghiệm nhiều kết hợp song song với nhau hơn. Nếu bạn biết một ô đã cho phải chứa 5, 7 hoặc XNUMX, bạn có thể tách vấn đề ra và kiểm tra đồng thời từng khả năng trong ba khả năng trên các nhóm máy tính khác nhau.

Đến tháng 2022 năm 13, những cải tiến này đã cho phép Heule và Subercaseaux loại trừ 14 là đáp án cho vấn đề tô màu bao bì trong một thử nghiệm cần thời gian tính toán chưa đến hai ngày. Điều này khiến họ có hai câu trả lời khả thi: 15 hoặc XNUMX.

Một điểm cộng lớn

Để loại trừ 14 — và giải quyết vấn đề — Heule và Subercaseaux phải tìm thêm các cách khác để tăng tốc độ tìm kiếm trên máy tính.

Ban đầu, họ đã viết một công thức Boolean gán các biến cho từng ô riêng lẻ trong lưới. Nhưng vào tháng 2022 năm XNUMX, họ nhận ra rằng họ không cần phải tiến hành trên cơ sở từng tế bào. Thay vào đó, họ phát hiện ra rằng sẽ hiệu quả hơn khi xem xét các vùng nhỏ bao gồm năm ô theo hình dấu cộng.

Họ đã viết lại công thức Boolean của mình sao cho một số biến đại diện cho các câu hỏi như: Có số 7 ở đâu đó trong vùng hình dấu cộng này không? Máy tính không cần xác định chính xác số 7 có thể ở đâu trong khu vực. Nó chỉ cần xác định xem nó có ở đó hay không — một câu hỏi cần ít tài nguyên máy tính hơn để trả lời.

Heule cho biết: “Việc có các biến chỉ nói về điểm cộng thay vì vị trí cụ thể hóa ra lại tốt hơn nhiều so với việc nói về chúng trong các ô cụ thể.

Được hỗ trợ bởi tính hiệu quả của tìm kiếm cộng, Heule và Subercaseaux đã loại trừ 14 trong một thử nghiệm trên máy tính vào tháng 2022 năm 13. Thử nghiệm này cuối cùng mất ít thời gian hơn so với thử nghiệm mà họ đã sử dụng để loại trừ XNUMX. Họ đã dành bốn tháng tiếp theo để xác minh điều đó kết luận của máy tính là chính xác - gần bằng thời gian họ đã dành để cho phép máy tính đi đến kết luận đó ngay từ đầu.

“Thật hài lòng khi nghĩ rằng những gì chúng tôi tạo ra như một loại câu hỏi phụ trong một tạp chí ngẫu nhiên nào đó đã khiến nhiều nhóm người, hóa ra, mất hàng tháng trời để cố gắng tìm ra cách giải quyết nó,” Goddard nói.

Đối với Subercaseaux, đó là chiến thắng thực sự đầu tiên trong sự nghiệp nghiên cứu của ông. Và mặc dù đó có thể không phải là kiểu khám phá mà anh ấy đã lý tưởng hóa khi lần đầu tiên dự tính làm việc trong toán học, nhưng cuối cùng thì anh ấy cũng nhận thấy rằng nó có những phần thưởng trí tuệ của riêng nó.

Anh ấy nói: “Thật không hiểu về hình thức mà bạn đưa cho tôi một tấm bảng đen và tôi có thể chỉ cho bạn lý do tại sao lại là 15. “Nhưng chúng tôi đã hiểu được cách vận hành của các ràng buộc của bài toán, việc có điểm 6 ở đây hay điểm 7 ở đó tốt hơn bao nhiêu. Chúng tôi đã đạt được rất nhiều hiểu biết trực quan.”