GPT-5.6 Pro bác bỏ giả thuyết Dinitz-Garg-Goemans

Dmitry Rybin công bố trên X rằng GPT-5.6 Pro đã tạo ra một phản ví dụ cho giả thuyết Dinitz-Garg-Goemans, bài toán mở trong tối ưu tổ hợp suốt khoảng 30 năm.

Bằng chứng khái niệm chỉ là một đồ thị nhỏ: luồng phân số (fractional flow) có chi phí 58, trong khi luồng không thể chia nhỏ (unsplittable flow) hợp lệ có chi phí 60. Hai điểm chênh lệch, ba thập kỷ, bốn prompt.

Tóm tắt các điểm chính

• GPT-5.6 Pro tạo ra một đồ thị có hướng nhỏ với một nguồn và ba điểm giao hàng, nơi luồng phân số tốn chi phí 58 còn luồng không chia nhỏ hợp lệ tốn ít nhất 60
• Kết quả chưa qua bình duyệt, Rybin công khai toàn bộ hội thoại ChatGPT để bất kỳ ai cũng có thể tự kiểm tra
• Định lý gốc năm 1999 của Dinitz, Garg và Goemans về giới hạn tắc nghẽn (congestion) vẫn không bị ảnh hưởng, chỉ có phần giả thuyết về chi phí (cost) bị thách thức
• Đây là giả thuyết toán học thứ ba được báo cáo sụp đổ nhờ hỗ trợ AI trong khoảng ba tháng gần đây, sau Jacobian conjecture với Claude Fable 5 và giả thuyết khoảng cách đơn vị Erdős
• Mô hình thất bại ba lần đầu tiên và trung thực báo cáo thất bại, chỉ đến prompt thứ tư mới tạo ra được cấu trúc hoạt động

Câu trả lời nhanh cho việc này là gì?

Rybin báo cáo rằng GPT-5.6 Pro, được định hướng bởi bốn prompt tổng cộng dưới 60 từ, đã tạo ra một phản ví dụ được cho là bác bỏ giả thuyết về chi phí của Goemans, bài toán mở từ khoảng năm 1999. Trường hợp cụ thể của ông là một đồ thị có hướng nhỏ với một nguồn duy nhất và ba điểm giao hàng. Ông khẳng định luồng có thể chia nhỏ (phân số) tốn chi phí 58, trong khi bất kỳ luồng không thể chia nhỏ nào giữ được mức tắc nghẽn trong ngân sách cho phép đều tốn ít nhất 60. Khoảng cách hai điểm đó, nếu vượt qua được quá trình rà soát chính thức, đủ để đánh sập giả thuyết.

Kết quả này chưa qua bình duyệt. Rybin công bố toàn bộ hội thoại ChatGPT để bất kỳ ai cũng có thể đọc cấu trúc, và nhiều người đã kiểm tra phép tính của ông và thấy nhất quán. Tuy nhiên, phép tính có thể tái lập và một chứng minh được chấp nhận là hai thứ khác nhau, và khoảng cách giữa chúng chính là trọng tâm của toàn bộ bài viết này.

Giả thuyết Dinitz-Garg-Goemans là gì?

Trước khi hiểu được điều gì đã sụp đổ, hoặc có thể đã sụp đổ, cần hiểu rõ giả thuyết này thực sự nói gì.

Hãy hình dung một kho hàng vận chuyển đơn hàng đến ba thị trấn qua một mạng lưới đường. Nếu được phép chia nhỏ một lô hàng, có thể gửi một nửa đơn hàng theo con đường này và nửa còn lại theo con đường khác. Đó là định tuyến phân số (fractional routing), linh hoạt và thường tìm được tập hợp đường đi rẻ hơn. Nhưng phần lớn hàng hóa thực tế không thể chia nhỏ. Một đơn hàng, một xe tải, một con đường, từ đầu đến cuối. Đó là luồng không thể chia nhỏ (unsplittable flow), và đây chính là điều mà một đơn hàng vận chuyển, một gói tin mạng, hay một container thực sự phải tuân theo.

Câu hỏi mà mọi người đã trăn trở từ năm 1999 khá đơn giản để phát biểu: nếu tồn tại một định tuyến phân số rẻ, liệu có luôn tìm được một định tuyến không thể chia nhỏ cũng rẻ mà không làm quá tải đường quá nghiêm trọng hay không?

Yefim Dinitz, Naveen Garg và Michel Goemans đã giải quyết được một nửa câu hỏi này. Nửa còn lại là phần GPT-5.6 nhắm đến. Để hiểu vì sao sự phân biệt này quan trọng đến vậy, cần làm rõ chính xác nó.

Định lý và giả thuyết khác nhau ở điểm nào?

Đây là sự phân biệt mà phần lớn bài viết khác thường làm mờ nhạt, nên sẽ được làm rõ một lần ở đây và dùng xuyên suốt bài viết.

Dinitz, Garg và Goemans đã chứng minh một kết quả về tắc nghẽn: cho một luồng phân số hợp lệ, luôn có thể chuyển đổi nó thành một luồng không thể chia nhỏ mà không vượt quá công suất bất kỳ con đường nào nhiều hơn mức nhu cầu lớn nhất duy nhất, gọi con số đó là D. Định lý đó không hề bị nghi ngờ và chưa bao giờ bị nghi ngờ.

Điều Goemans riêng biệt đặt ra là phiên bản mạnh hơn, có tính đến chi phí: rằng cùng một phép chuyển đổi đó cũng có thể giữ tổng chi phí ở mức thấp trong khi vẫn giữ mức tắc nghẽn thấp. Tắc nghẽn và chi phí, cả hai đều bị chặn, trong cùng một lần định tuyến. Định lý chỉ về tắc nghẽn vẫn an toàn. Giả thuyết chi phí cộng tắc nghẽn mới là phần mà Rybin nói đã sụp đổ. Nếu chỉ nhớ một câu từ bài viết này, hãy nhớ câu đó. Nhiều bài đưa tin phấn khích đã âm thầm đánh tráo hai khái niệm này, và sự khác biệt giữa chúng chính là toàn bộ khoảng trống toán học mất 30 năm mới được thu hẹp.

GPT-5.6 thực sự đã xây dựng được gì?

Trường hợp của Rybin đủ nhỏ để mô tả trong một đoạn văn. Một nguồn, vài node trung gian tạo thành một "xương sống" chung, và ba điểm giao hàng, mỗi điểm mang một nhu cầu. Mỗi điểm giao hàng có hai đường về nhà: một đường trực tiếp đắt tiền, hoặc một đường vòng miễn phí qua xương sống chung.

Sự căng thẳng ở đây mang tính cấu trúc. Các đường vòng rẻ cạnh tranh chỗ trên xương sống, nên nếu quá nhiều điểm giao hàng cùng cố định tuyến rẻ, một con đường thuộc xương sống sẽ quá tải. Đẩy điều này đủ xa, chỉ một điểm giao hàng có thể đi đường rẻ trong bất kỳ định tuyến không thể chia nhỏ hợp lệ nào. Các điểm còn lại buộc phải đi đường trực tiếp đắt tiền, và chi phí tăng lên. Luồng phân số, được tự do chia nhỏ, trải mỗi nhu cầu ra cả hai đường và lách dưới mọi giới hạn công suất cùng lúc. Đó là cách để có được chi phí phân số thấp hơn chi phí không thể chia nhỏ hợp pháp rẻ nhất. Con số của Rybin cho trường hợp của ông là 58 và 60.

Cần thành thật về một giới hạn ở đây. Chưa thể tái tạo chính xác đồ thị của Rybin, các công suất cụ thể và các xung đột theo cặp, từ một nguồn gốc chính thức. Bản ghi hội thoại của ông mô tả một điểm cụ thể trong một họ tham số, và mô tả "bảy node" được chia sẻ rộng rãi là một sự trừu tượng hóa của nó, không phải một cấu trúc đã được xác minh từng cạnh một. Vì vậy sẽ không dựng lên một suy luận gọn gàng cho ra 58 rồi giả vờ đó là của ông. Điều có thể làm là đưa ra một trường hợp tự chứa cho thấy cùng cơ chế đó, đủ nhỏ để kiểm tra bằng brute force, để có thể thấy tận mắt "phân số thắng mọi luồng không thể chia nhỏ hợp lệ" trông như thế nào.

Bốn prompt và nhiều giờ đã diễn ra như thế nào?

Số lượng prompt là chi tiết ít thú vị nhất trong câu chuyện này, dù đây lại là phần lan truyền nhanh nhất.

Bản ghi chat mà Rybin chia sẻ cho thấy mô hình thất bại trước, và thất bại một cách chính xác. Prompt đầu tiên yêu cầu tìm một phản ví dụ có cấu trúc. Mô hình làm việc gần một giờ đồng hồ và trả về tay không, tuyên bố thẳng thắn rằng trình bày những gì đã có như một phản ví dụ hợp lệ sẽ là sai sự thật.

Được yêu cầu tiếp tục, mô hình chạy lại, và một lần nữa báo cáo không có gì, mô tả cách mỗi cấu trúc có triển vọng liên tục mọc thêm một tùy chọn định tuyến ẩn phá vỡ sự tách biệt chi phí-tắc nghẽn một khi mọi đường đi được liệt kê hết. Prompt thứ ba yêu cầu một chiến lược gọn gàng hơn mang lại một khung làm việc thu hẹp hơn nhưng vẫn chưa có kết quả hoàn chỉnh.

Đó không phải "bốn prompt, xong." Đó là nhiều giờ đồng hồ một mô hình liên tục đâm vào tường và trung thực báo cáo về điều đó. Bức tường cụ thể mà mô hình liên tục đâm vào, một đường đi thêm xuất hiện và phá hỏng sự tách biệt, chính là điều mà cấu trúc cuối cùng được xây dựng để ngăn chặn, bằng cách gắn chặt mỗi điểm giao hàng vào chính xác hai đường đi, để toàn bộ không gian định tuyến chỉ còn tám lựa chọn có thể liệt kê bằng tay. Hãy ghi nhớ kiểu thất bại này. Người đọc sắp tự gặp phải nó.

Prompt thứ tư, được cho là gần giống với "đã chán ngán thất bại của bạn rồi, hãy hoàn thành với một phản ví dụ đầy đủ, vô điều kiện", chính là prompt tạo ra cấu trúc hoạt động, kèm theo chứng chỉ chứng minh, một chương trình liệt kê, và LaTeX đầy đủ. Sự kiên nhẫn có ý nghĩa. Những lần từ chối trước đó cũng vậy, chúng là những tự đánh giá trung thực.

Có thể tự kiểm tra kết quả này không?

Đây là nơi bài viết của Infinity có thể làm được điều mà một bài tin tức không làm được: để người đọc tự chạy phép xác minh.

Một lưu ý nhanh trước phần code. Nội dung dưới đây không phải đồ thị của Rybin. Đây là một trường hợp mang tính sơ đồ được xây dựng để trung thực, một trường hợp mà mỗi điểm giao hàng thực sự chỉ có đúng hai đường đi, phép tính khép kín, và khoảng cách là có thật. Nó cho thấy hình dạng của một phản ví dụ như vậy và kỹ thuật để kiểm tra một trường hợp, tự bản thân nó không bác bỏ điều gì cả, và lý do sẽ được giải thích ngay sau khi chạy nó.

Cấu hình: ba điểm giao hàng, mỗi điểm vận chuyển 10 đơn vị, nên nhu cầu lớn nhất D là 10. Mỗi điểm có một đường trực tiếp đắt (chi phí 30) và một đường rẻ miễn phí. Các đường rẻ được sắp xếp sao cho mỗi cặp trong số chúng tranh giành một con đường nút cổ chai riêng: đường A dùng chung bởi điểm 1 và 2, đường B bởi điểm 1 và 3, đường C bởi điểm 2 và 3. Trong luồng phân số, mỗi điểm giao hàng gửi 2/5 nhu cầu theo đường rẻ và 3/5 theo đường đắt, tốn chi phí 30 x 3/5 x 3 = 54. Mỗi con đường khi đó mang 4 + 4 = 8 đơn vị theo tỷ lệ phân số, và ngân sách tắc nghẽn là tải trọng đó cộng D, tức 18.

Giờ hãy xem điều gì xảy ra khi định tuyến không thể chia nhỏ. Hai điểm giao hàng cùng đi đường rẻ đổ 10 + 10 = 20 đơn vị lên con đường dùng chung, vượt ngân sách 18. Nên nhiều nhất chỉ một điểm giao hàng có thể định tuyến rẻ, hai điểm còn lại phải trả 30 mỗi điểm. Chi phí không thể chia nhỏ hợp pháp tối thiểu: 60. So với phân số là 54. Tồn tại tám cách định tuyến, nên chỉ cần kiểm tra hết tất cả:

from itertools import product

# Ba điểm giao hàng, mỗi điểm có nhu cầu 10 -> nhu cầu lớn nhất D = 10.
# Mỗi điểm có một đường rẻ (chi phí 0) và một đường trực tiếp đắt (chi phí 30).
# Các đường rẻ theo cặp dùng chung một con đường nút cổ chai RIÊNG, nên mỗi cặp xung đột:
#   đường A dùng chung bởi {t1, t2}, đường B bởi {t1, t3}, đường C bởi {t2, t3}
# LƯU Ý: đây là trường hợp mang tính sơ đồ để minh họa phép kiểm tra, không phải đồ thị của Rybin.

demands = [10, 10, 10]
d_max = max(demands)          # khoảng dư tắc nghẽn cho phép trên mỗi đường
cheap_frac = [2/5, 2/5, 2/5]  # phần đắt là 3/5 mỗi điểm -> chi phí phân số 54
direct_cost = 30              # chi phí của đường đắt một điểm giao hàng

# Mỗi điểm giao hàng dùng đường rẻ trên những con đường nút cổ chai nào
uses = [
    {"A": True,  "B": True,  "C": False},  # t1: A, B
    {"A": True,  "B": False, "C": True},   # t2: A, C
    {"A": False, "B": True,  "C": True},   # t3: B, C
]

# Luồng phân số làm bão hòa mỗi con đường, nên tải trọng bằng đúng công suất con đường đó
cap = {"A": 0.0, "B": 0.0, "C": 0.0}
for i in range(3):
    for road in cap:
        if uses[i][road]:
            cap[road] += cheap_frac[i] * demands[i]   # 8 đơn vị mỗi con đường

# Quy tắc tắc nghẽn: một luồng không thể chia nhỏ được phép vượt công suất tối đa D
threshold = {road: cap[road] + d_max for road in cap}  # 18 mỗi con đường

fractional_cost = sum(direct_cost * (1 - cheap_frac[i]) for i in range(3))  # 54

print(f"Công suất (tải phân số): {cap}")
print(f"Ngân sách tắc nghẽn mỗi đường: {threshold}")
print(f"Chi phí luồng phân số: {fractional_cost}\n")
print(f"{'Định tuyến (0=rẻ,1=đắt)':22} {'Chi phí':>4} {'A':>3} {'B':>3} {'C':>3}  Hợp lệ")

valid_costs = []
for choices in product([0, 1], repeat=3):    # 0 = rẻ, 1 = đắt
    cost = sum(direct_cost * c for c in choices)
    load = {"A": 0, "B": 0, "C": 0}
    for i, expensive in enumerate(choices):
        if expensive == 0:                    # điểm này đi đường rẻ
            for road in load:
                if uses[i][road]:
                    load[road] += demands[i]
    ok = all(load[road] <= threshold[road] for road in load)
    tag = "OK" if ok else "quá tải"
    print(f"{str(choices):22} {cost:>4} {load['A']:>3} {load['B']:>3} {load['C']:>3}  {tag}")
    if ok:
        valid_costs.append(cost)

print(f"\nChi phí không thể chia nhỏ hợp lệ nhỏ nhất: {min(valid_costs)}")
print(f"Khoảng cách: {min(valid_costs) - fractional_cost} (phản ví dụ nếu > 0)")

Chạy đoạn code này sẽ cho ra chi phí phân số là 54, chi phí không thể chia nhỏ hợp pháp tối thiểu là 60, và khoảng cách là 6. Ba dòng bị quá tải chính là ba xung đột theo cặp, chỉ những cách định tuyến còn sống sót giữ nhiều nhất một điểm giao hàng đi đường rẻ.

Vậy giả thuyết đã chết chưa? Chưa hẳn, và đây là phần đã hứa sẽ giải thích. Lượt liệt kê tám dòng đó chỉ đúng nếu mỗi điểm giao hàng thực sự chỉ có hai đường đi và không hơn. Xây đồ thị này từ những con đường và node thực tế, một đường rẻ thứ tư có xu hướng xuất hiện từ chính bản chất tổ hợp. Một điểm giao hàng tìm ra một con đường thứ ba về nhà vừa rẻ vừa nằm trong ngân sách, và khoảng cách khép lại. Con đường thừa đó chính là thất bại mà mô hình đã báo cáo trong ba lần thử đầu tiên. Một gadget gọn gàng, đối xứng, phá vỡ một giả thuyết 30 năm chỉ trong tám dòng Python sẽ là quá tốt để là sự thật, và đúng là vậy. Đoạn code trên chứng minh phương pháp kiểm tra là hợp lý và tính chất mục tiêu là có thật. Việc một đồ thị cụ thể có thực sự sở hữu tính chất đó, không rò rỉ, mới là phần khó, và đó là lý do trường hợp thực tế của Rybin là một điểm được tinh chỉnh trong một họ tham số, chứ không phải một tam giác gọn gàng.

Điều gì vẫn còn chưa được giải quyết?

Chưa có bài báo chính thức nào xuất hiện. Rybin chia sẻ cuộc hội thoại và cấu trúc, nhưng cả hai chưa qua quy trình phản biện có thể cho phép cộng đồng toán học chính thức khép lại giả thuyết này.

Đồ thị chính xác đã công bố chưa được tái dựng độc lập từ một nguồn gốc chính thức có thể tìm thấy. Các con số đang lan truyền đến từ bài đăng và bản ghi hội thoại được chia sẻ của ông. Nhiều nhà nghiên cứu đã kiểm tra phép tính của ông và cho là nhất quán, và một người đã chỉ ra trường hợp của ông nằm trong một họ tham số ba biến vô hạn trên cùng bộ node, điều này khiến kết quả trở nên phong phú hơn một sự trùng hợp may mắn đơn lẻ. Đáng khích lệ, nhưng đó là kiểm tra không chính thức từ cộng đồng, không phải một báo cáo phản biện. Nên xem con số 58 so với 60 như một tuyên bố được hỗ trợ tốt, không phải một sự thật đã được xác lập.

Định lý tắc nghẽn năm 1999 hoàn toàn không bị ảnh hưởng bởi bất kỳ điều gì trong số này.

Đây có phải một phần của một xu hướng lớn hơn không?

Câu chuyện này không phải một điểm dữ liệu đơn lẻ. Đây là giả thuyết thứ ba được báo cáo sụp đổ nhờ sự hỗ trợ của AI trong khoảng ba tháng, và mẫu hình này đáng để dừng lại xem xét.

• Ngày 20/7, Claude Fable 5 được cho là đã giúp nhà toán học Levent Alpöge tìm ra một phản ví dụ cho giả thuyết Jacobian, bài toán tồn đọng 87 năm.
• Trước đó, vào tháng 5, một mô hình của OpenAI được cho là đã bác bỏ giả thuyết khoảng cách đơn vị Erdős tồn tại 80 năm.
• Cùng tuần với tin tức này, một nghiên cứu sinh tiến sĩ tại Columbia đã dùng GPT-5.6 với một workflow Codex có cấu trúc để giải quyết sáu bài toán mở của Erdős trong năm ngày.

Mạch xuyên suốt, như một nhà nghiên cứu diễn đạt, là các hệ thống này giỏi bác bỏ hơn là chứng minh. Một phản ví dụ là một nhân chứng duy nhất có thể kiểm tra, còn một chứng minh phải bao phủ mọi trường hợp. Sự bất đối xứng đó dường như quyết định bài toán nào sụp đổ trước.

Bài học thực tiễn không phải "AI giải được toán". Điều đang chứng kiến là AI hoạt động như một đối tác tìm kiếm kiên nhẫn, bao phủ toàn diện về mặt tổ hợp: có thể liệt kê các họ tham số, giữ các kiểu thất bại trong bộ nhớ làm việc qua nhiều lần thử, và nói thật khi một cấu trúc không khép lại. Đó là một năng lực cụ thể, hữu ích. Nếu muốn hiểu điều này có khả năng chạm tới đâu tiếp theo, câu hỏi cần đặt ra không phải giả thuyết nào lâu đời nhất, mà là giả thuyết nào có thể bị đánh sập bởi một nhân chứng duy nhất, có thể kiểm tra được.

Câu hỏi thường gặp

GPT-5.6 Pro chính xác đã tuyên bố bác bỏ điều gì?

Giả thuyết chi phí của Goemans, tuyên bố rằng bất kỳ luồng có thể chia nhỏ nào cũng có thể chuyển thành một luồng không thể chia nhỏ giữ cả tắc nghẽn lẫn chi phí ở mức thấp cùng lúc. Rybin báo cáo một trường hợp mà định tuyến phân số tốn chi phí 58, còn mọi định tuyến không thể chia nhỏ hợp pháp về tắc nghẽn đều tốn ít nhất 60. Định lý Dinitz-Garg-Goemans năm 1999 riêng biệt, vốn chỉ giới hạn tắc nghẽn, không bị ảnh hưởng.

Điều này đã được các nhà toán học xác minh chưa?

Nhiều người đã kiểm tra phép tính và cho là nhất quán, và một người đã đặt trường hợp này vào trong một họ tham số vô hạn. Nhưng chưa có bài báo qua bình duyệt nào xuất hiện, nên giả thuyết chưa chính thức khép lại. Tuyên bố này đủ để kiểm tra được, nên người đọc không cần phải tin lời ai về cơ chế, đó chính xác là mục đích của phần code.

Đoạn code cho ra khoảng cách dương. Điều đó không bác bỏ giả thuyết sao?

Không, và sẽ gây hiểu lầm nếu để đoạn đó được đọc theo hướng đó. Đoạn code kiểm tra một trường hợp mang tính sơ đồ nơi mỗi điểm giao hàng có đúng hai đường đi theo cấu trúc đã dựng sẵn. Các đồ thị thực tế có hình dạng này có xu hướng rò rỉ thêm một đường rẻ, xóa bỏ khoảng cách đó, đúng vấn đề mà mô hình gặp phải trong ba lần thử đầu tiên. Đoạn code chứng minh phương pháp xác minh là hợp lý và tính chất mục tiêu là có thật, nó không chứng nhận rằng bất kỳ đồ thị cụ thể nào, kể cả đồ thị trong bài này, không có rò rỉ.

Vì sao mô hình thất bại ba lần đầu tiên?

Theo bản ghi hội thoại, mỗi cấu trúc mà mô hình thử đều liên tục có thêm một tùy chọn định tuyến ẩn một khi mọi đường đi được liệt kê hết, và tùy chọn đó luôn cung cấp một lối thoát rẻ giết chết khoảng cách chi phí. Cấu trúc cuối cùng tránh được điều này bằng cách gắn chặt mỗi điểm giao hàng vào chính xác hai đường đi, để tổng cộng tám cách định tuyến có thể được kiểm tra toàn diện mà không còn chỗ trốn.

Điều này có thay đổi gì với định tuyến mạng thực tế không?

Không trực tiếp. Kỹ sư đã dùng các thuật toán xấp xỉ với những đánh đổi đã biết. Nếu kết quả này đứng vững, nó xác nhận một giới hạn lý thuyết, rằng không thuật toán nào có thể đảm bảo bảo toàn chi phí và tính chất tắc nghẽn bị chặn trong mọi trường hợp tổng quát, điều này chủ yếu cho các nhà lý thuyết biết ranh giới nằm ở đâu.

Nguồn: Infinity - đơn vị cung cấp giải pháp Digital Marketing tích hợp cho doanh nghiệp — từ thiết kế website chuẩn SEO & UX/UI, dịch vụ AI SEO (GEO/AEO), PR Digital, sáng tạo nội dung số, quảng cáo trực tuyến (SEM/Ads) đến phân tích dữ liệu Marketing. Với nền tảng nghiên cứu và dữ liệu thực chiến, chúng tôi giúp doanh nghiệp xây dựng chiến lược thương hiệu bền vững và tăng trưởng có hệ thống trong kỷ nguyên AI.