Lại nữa??? GPT-5.6 gần đây rõ ràng đã đụng phải tổ các phản ví dụ toán học...
Một giả thuyết Dinitz-Garg-Goemans tồn tại trong lĩnh vực lý thuyết đồ thị gần 30 năm vừa được GPT-5.6 Pro tìm ra phản ví dụ.
Một nhà nghiên cứu tên Dmitry Rybin, trong suốt quá trình lập luận, chỉ nhập tổng cộng 4 lời nhắc, tổng cộng 58 từ tiếng Anh.
Không có hàng ngàn từ về kỹ thuật prompt, không có công thức phức tạp, toàn bộ bài viết cơ bản đều là:
Tiếp tục nghiên cứu, tiếp tục tìm, cho tôi một phản ví dụ hoàn chỉnh!!!
Tiếp tục đẩy như vậy từng vòng một, GPT-5.6 Pro đã đưa ra một kết luận cực kỳ ấn tượng—
Giả thuyết Dinitz-Garg-Goemans là sai.
Sản phẩm cuối cùng do AI giao bao gồm một sơ đồ minh họa, bốn chứng nhận xác minh, chương trình xác minh đầy đủ chính xác, dữ liệu phản ví dụ có thể đọc được bằng máy và mã nguồn LaTeX.
Sau đó, một giả thuyết toán học đã tồn tại gần 30 năm, lại bị mấy câu “bùa sát mạng” này khiến bộc lộ lỗ hổng chết người???
Giả thuyết trong gần 30 năm, bị GPT-5.6 Pro phát hiện lỗi nghiêm trọng
Chúng ta hãy nói trước rằng, giả thuyết Dinitz-Garg-Goemans với cái tên dài ngoằng này đang nghiên cứu cái gì.
Chúng ta có thể tưởng tượng trực tiếp nó như một “bài toán giao hàng”.
Giả sử một kho hàng cần giao hàng đến nhiều điểm đến, khi cho phép chia lô, cùng một lô hàng có thể được chia ra đi theo nhiều tuyến đường—
Một nửa đi cao tốc, một nửa đi quốc lộ, miễn là cuối cùng đều giao đầy đủ là được～
Nhưng theo quy tắc không chia tách, mỗi lô hàng phải đi trọn vẹn một tuyến đường, không được chia nhỏ!!!
Thực tế, tình huống này không hề hiếm gặp, chẳng hạn như dữ liệu mạng, đơn hàng logistics, điều phối giao thông và phân bổ chuỗi cung ứng đều gặp phải các vấn đề tương tự:
Giải pháp tối ưu về mặt toán học có thể chia nhiệm vụ thành vô số phần nhỏ, nhưng trong thực tế, một chiếc xe hay một đơn hàng không thể bị chia thành 0,37 phần.
△
Và một khi việc chia tách bị cấm, phương án tối ưu trước đây cũng khó có thể áp dụng trực tiếp.
Hàng hóa trước đây được phân tán trên nhiều con đường, giờ đây phải được nén vào một tuyến đường duy nhất, khiến tải trọng trên một số tuyến đường có thể tăng đột ngột.
Vì vậy, vấn đề thực sự cần giải quyết là:
Làm thế nào để chuyển đổi phương án “có thể chia nhỏ để vận chuyển” thành “phải vận chuyển nguyên lô”, đồng thời không khiến giao thông bị ùn tắc nghiêm trọng?
Năm 1999, Yefim Dinitz, Naveen Garg và Michel Goemans đã công bố bài báo kinh điển trong lĩnh vực dòng chảy không phân chia một nguồn và chứng minh rằng sự tắc nghẽn này có thể được kiểm soát trong một phạm vi nhất định.
Nhưng sau khi giải quyết được vấn đề “có bị nghẽn quá nặng không?”, vẫn còn một vấn đề thực tế khác: liệu có trở nên đắt hơn không?
Do đó, học giả nổi tiếng trong lĩnh vực tối ưu hóa tổ hợp Goemans đã đề xuất một phiên bản mạnh hơn có chi phí—
While maintaining the above overload limit, the total cost should also not exceed that of the original分流方案.
Nói đơn giản là, trước đây chia nhỏ để vận chuyển có thể vừa rẻ vừa không bị kẹt nhiều, vậy bây giờ yêu cầu mỗi lô hàng phải đi trọn vẹn một tuyến đường, về lý thuyết cũng nên tìm được một phương án tương tự rẻ tiền và chỉ bị kẹt nhiều nhất một lô hàng.
Tuy nhiên, phỏng đoán dường như khá trực quan này vẫn chưa được chứng minh trên các cấu trúc đồ thị tổng quát, và các nghiên cứu sau này chỉ mới giải quyết được một số trường hợp đặc biệt.
Nhiều năm sau, giả thuyết này vẫn chưa được chứng minh hay bác bỏ.
Ví dụ phản chứng do GPT-5.6 Pro đưa ra đúng lúc làm cho hai điều kiện trong giả thuyết không thể đồng thời xảy ra:
Không thể quá ùn tắc, cũng không thể trở nên đắt đỏ.
Nó tạo ra một đồ thị nhỏ gồm 7 nút và 9 cạnh có hướng, với một điểm xuất phát chung và ba điểm đến, nhu cầu của ba lô hàng lần lượt là 15, 10 và 15:
Mỗi lô hàng đều có hai tuyến đường tùy chọn:
Một tuyến đường có chi phí cao, mỗi đơn hàng hoàn thành đều tốn 30; tuyến đường khác có chi phí bằng 0, nhưng cần chia sẻ một phần đường với các đơn hàng khác.
Nếu được chia tách, ba lô hàng có thể một phần đi theo tuyến có phí, một phần đi theo tuyến miễn phí, với tổng chi phí cuối cùng là 58.
nhưng! Khi yêu cầu mỗi lô hàng phải chọn đầy đủ một tuyến đường, rắc rối sẽ đến…
Kết luận từ GPT-5.6 Pro cho thấy, giữa ba tùy chọn miễn phí thực sự có xung đột từng đôi một!
Chọn đồng thời hai lô hàng trên tuyến miễn phí sẽ cùng chen vào một đoạn đường nhất định, khiến tải thực tế đạt 25, 30 hoặc 40; trong khi giới hạn cho phép của các đoạn đường tương ứng lần lượt chỉ là 24, 29 hoặc 39.
Mỗi lần, đều vừa đúng dư ra 1 đơn vị.
Vì vậy, để duy trì giới hạn tải quy định trong giả thuyết, tối đa chỉ có một lô hàng trong ba lô có thể chọn con đường miễn phí.
Hai lô hàng còn lại đều phải chọn tuyến có phí.
Chi phí mỗi lô là 30, tổng chi phí của hai lô, bất kỳ giải pháp nào đáp ứng yêu cầu tải, chi phí tối thiểu cũng là: 60.
Điều này tạo ra một tình thế không thể đồng thời thỏa mãn: muốn kiểm soát tải đường bộ trong phạm vi quy định, chi phí tối thiểu phải là 60; muốn giảm chi phí trở lại mức 58 ban đầu, ít nhất một con đường sẽ vượt quá giới hạn.
Và giả thuyết này chính xác cho rằng có thể đồng thời thực hiện cả hai điều kiện này.
Moreover, verifying this counterexample isn't as complicated as it might seem.
Ba điểm đến, mỗi điểm có hai lộ trình, tổng cộng chỉ có 2³ = 8 tổ hợp.
Liệt kê từng trong 8 khả năng, bạn sẽ thấy 4 trường hợp đáp ứng yêu cầu về dung lượng, với chi phí lần lượt là 90, 60, 60 và 60; 4 trường hợp còn lại tuy rẻ hơn nhưng đều gây quá tải đường bộ.
All scenarios have been exhaustively checked, and there are no hidden paths missed.
Nói cách khác, chỉ cần định nghĩa của biểu đồ này hoàn toàn nhất quán với các điều kiện của giả thuyết ban đầu, khoảng trống hai đơn vị giữa 58 và 60 đã đủ để bác bỏ giả thuyết.
Bốn lần thúc giục điên cuồng, cuối cùng cũng ép được GPT-5.6 đưa ra ví dụ phản chứng
Điều thú vị nhất của sự việc thực ra ẩn chứa trong cuộc đối thoại công khai giữa Rybin và GPT-5.6 Pro.
Khi thấy một giả thuyết toán học đã tồn tại gần 30 năm bị AI bác bỏ, tôi tự nhiên nghĩ rằng phía sau chắc chắn phải có một bộ chuỗi hướng dẫn cực kỳ phức tạp luân phiên sử dụng!!!
Thực ra, chúng ta vẫn là đại E.
Vì yêu cầu đầu tiên Rybin đưa cho GPT-5.6 Pro, ngoài tệp đính kèm ra, phần còn lại thực sự là ngôn ngữ cực kỳ đơn giản:
Vâng, đơn giản như vậy.
Sau đó, GPT-5.6 Pro bắt đầu tuân theo lệnh và làm việc chăm chỉ.
Nó đã xây dựng một phương pháp xác minh quy hoạch tuyến tính, sau đó thử nghiệm nhiều cấu trúc khác nhau như siêu lập phương, đồ thị phân tầng, mạng hợp nhất—phân nhánh, và đã sàng lọc hàng ngàn ví dụ nhỏ.
Sau một hồi tìm kiếm kỹ lưỡng, câu trả lời đầu tiên mà mô hình đưa ra lại là: Không tìm thấy phản ví dụ nào hiệu quả. (doge)
Ngay cả GPT-5.6 Pro cũng cảnh báo nghiêm túc rằng, nếu đóng gói các cấu trúc xấp xỉ tìm được ở giai đoạn hiện tại thành phản ví dụ, sẽ dẫn đến một kết luận toán học sai lầm.
Tôi đã cố gắng hết sức, nhưng hiện tại thật sự không thể giải được bài này!!!
Nhân vật chính trong câu chuyện của chúng tôi, Rybin, không hề ăn theo cách đó, anh ấy không bổ sung công thức mới, cũng không tự mình dẫn đường, mà chỉ nhẹ nhàng đáp lại một câu:
Tiếp tục nghiên cứu để tìm một phản ví dụ đầy đủ và không điều kiện nhé~
Vì vậy, GPT-5.6 Pro lại chìm vào tìm kiếm một vòng nữa, nhưng vòng thứ hai vẫn thất bại.
Rybin tiếp tục thúc đẩy, yêu cầu nó dựa trên sự hiểu biết sâu sắc về cấu trúc vấn đề, trước tiên xây dựng chiến lược rõ ràng, sau đó mới tìm kiếm.
Đến vòng thứ ba, mô hình đã thu hẹp phạm vi tìm kiếm xuống còn một cấu trúc định tuyến chỉ có 24 trạng thái, dường như chỉ còn cách câu trả lời một bước nữa.
Tuy nhiên, AI này vẫn chưa đưa ra được phản ví dụ đầy đủ...
Lúc này, Rybin đã đưa ra gợi ý thứ tư: Một số kết quả đã đủ rồi, hãy kết thúc bằng một phản ví dụ đầy đủ và vô điều kiện.
Được rồi, nói đến mức này thì cũng hết lời rồi.
Lần này, GPT-5.6 Pro cuối cùng cũng đưa ra biểu đồ phản ví dụ gồm 7 nút và 9 cạnh có hướng—bốn lời nhắc, tổng cộng 58 từ tiếng Anh.
Không có cốt nhân vật vài nghìn chữ, cũng không thấy hàng chục quy định rườm rà, toàn bộ nội dung có thể tóm gọn thành:
Tôi đang nhắc! Tôi đang nhắc! Tôi tiếp tục nhắc!
Nhưng nếu dịch toàn bộ cuộc hội thoại từ đầu đến cuối, bạn sẽ thấy rằng GPT-5.6 Pro trong vài giờ qua cũng đã đi không ít đường vòng...
AI đã nhiều lần tìm thấy các ví dụ phản chứng dường như hợp lệ, nhưng khi nó liệt kê đầy đủ tất cả các con đường, lại phát hiện ra rằng mạng lưới ẩn chứa một số "con đường hỗn hợp" trước đó đã bị bỏ sót.
Các đường dẫn này sẽ lấy một đoạn từ các tuyến preset khác nhau, sau đó ghép lại để tạo ra cách đi mới, lén lút tránh khỏi giới hạn dung lượng mà mô hình ban đầu được thiết kế.
Kết quả là, ngay sau khi xác minh xong, ví dụ phản bác đã được thiết lập lại sụp đổ.
GPT-5.6 Pro cũng tóm tắt rất thành thật ở giữa chừng:
Việc chỉ kiểm tra vài trăm tuyến đường được định sẵn là chưa đủ. Một phản ví dụ thực sự hiệu quả phải tính đến tất cả các tuyến đường không thể phân luồng có thể xuất hiện trong mạng lưới.
This also makes the entire human-machine collaboration quite subtle.
表面上看, Rybin chỉ đóng góp 58 từ, nhưng hành động thực sự quan trọng là anh ấy có thể nhận ra ba vòng đầu tiên của mô hình đều chỉ là kết quả giai đoạn và liên tục từ chối kết thúc sớm.
Sau khi xem, giáo sư Wharton Ethan Mollick đã đặt ra một câu hỏi mới:
Người viết công việc này, rốt cuộc nên tính là Rybin đã viết 58 từ, hay GPT-5.6 Pro đã suy luận liên tục hàng giờ đồng hồ?
Thực tế, bất kể cách ghi danh cuối cùng ra sao, cuộc hội thoại này ít nhất đã đóng góp một kinh nghiệm sử dụng AI khá đơn giản—
Prompt hiệu quả nhất để thúc đẩy AI làm việc, đôi khi đơn giản đến mức chỉ cần khiến nó hóa thân thành con la, tiếp tục không ngừng đào bới.
Trong tuần qua, tốc độ AI tìm kiếm phản ví dụ toán học, từ giả thuyết Jacoby đến Dinitz-Garg-Goemans, thực sự đã bắt đầu trở nên hơi quá mức…
Bài viết này đến từ tài khoản chính thức WeChat "Quantum Bit", tác giả: Mộng Dao