GPT-5.6 và giả thuyết Dinitz-Garg-Goemans

Ngày 22 tháng 7 năm 2026, Dmitry Rybin đăng một tuyên bố trên X khiến một số người phải đặt tách cà phê xuống: GPT-5.6 Pro đã đưa ra một phản ví dụ cho giả thuyết Dinitz-Garg-Goemans, vốn là bài toán mở trong tối ưu tổ hợp suốt khoảng 30 năm. Bằng chứng ý tưởng là một đồ thị nhỏ. Chi phí luồng phân số là 58, chi phí luồng không thể tách là 60. Hai con số, ba thập kỷ, bốn lời nhắc.

Hầu hết các bài đưa tin đều lặp lại các con số mà không cho thấy cơ chế đằng sau chúng, trong khi chính cơ chế mới là nơi chứa bài học thực sự. Cũng là nơi tôi phải nói thẳng với bạn về điều đã được kiểm chứng và điều chưa. Tóm tắt: các khái niệm là vững, tin tức là một tuyên bố chứ chưa phải định lý, và nếu bạn ngồi xuống dựng lại chính xác đồ thị từ đầu, bạn sẽ hiểu ngay vì sao các bài toán như thế này khó ngay khoảnh khắc bản tái dựng của bạn bắt đầu "rò rỉ".

Câu trả lời nhanh

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

Nó chưa qua phản biện học thuật. Rybin đã công bố toàn bộ cuộc trò chuyện ChatGPT để ai cũng có thể đọc phần xây dựng, và vài người đã kiểm tra số học của anh và thấy nhất quán. Tuy nhiên, số học có thể tái lập và một chứng minh được chấp nhận là hai chuyện khác nhau, và khoảng cách giữa chúng chính là toàn bộ câu chuyện của bài viết này.

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

Trước khi hiểu cái gì đã sụp đổ, hoặc có thể đã sụp đổ, ta cần hiểu giả thuyết thực sự nói gì.

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

Câu hỏi mọi người cân nhắc từ năm 1999 rất dễ phát biểu. Nếu tồn tại một định tuyến có thể tách rẻ, liệu bạn luôn có thể tìm ra một định tuyến không thể tách cũng rẻ mà không làm quá tải các tuyến đường quá mức hay không?

Yefim Dinitz, Naveen Garg và Michel Goemans đã giải quyết một nửa. Nửa còn lại là phần GPT-5.6 nhắm tới. Để hiểu vì sao phân biệt đó là vô cùng quan trọng, ta cần nói thật chính xác.

Định lý so với giả thuyết

Đây là sự phân biệt mà đa số bài viết làm mờ, nên tôi sẽ nói chính xác một lần rồi dựa vào đó cho phần còn lại của bài.

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

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

GPT-5.6 thực sự đã xây gì

Trường hợp của Rybin đủ nhỏ để mô tả trong một đoạn. Một nguồn, vài nút trung gian tạo thành một “xương sống” dùng chung, và ba đích, mỗi đích mang một nhu cầu. Mỗi đích có hai lối về: 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 dùng chung.

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

Tôi xin nói thẳng về một giới hạn. Tôi chưa thể tái dựng chính xác đồ thị của Rybin, các sức chứa cụ thể và các xung đột từng cặp, từ nguồn sơ cấp. Bảng chép lại của anh mô tả một điểm cụ thể trong một họ tham số, và phần mô tả “bảy nút” được chia sẻ rộng rãi là một trừu tượng của nó, không phải một cấu trúc tôi đã kiểm chứng từng cạnh. Vậy nên tôi sẽ không dựng một phép suy ra gọn gàng con số 58 rồi giả như đó là của anh. Điều tôi có thể làm là đưa bạn một trường hợp độc lập thể hiện cùng cơ chế, đủ nhỏ để kiểm tra bằng vét cạn, để bạn tự mắt thấy “phân số thắng mọi luồng không thể tách hợp lệ” trông như thế nào. 

Bốn lời nhắc, vài giờ đồng hồ

Số lượng lời nhắc là phần kém thú vị nhất của câu chuyện này, dù đó lại là phần lan truyền mạnh.

Nhật ký trò chuyện 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. Lời nhắc mở đầu yêu cầu tìm một phản ví dụ có cấu trúc. Nó làm việc suốt gần một giờ và quay lại tay không, nói thẳng rằng nếu trình bày những gì nó có như một phản ví dụ hợp lệ sẽ là sai.

Khi được yêu cầu tiếp tục, nó chạy lại, và lại báo không có gì, mô tả cách mỗi cấu trúc có vẻ hứa hẹn đều mọc ra một lựa chọn định tuyến ẩn bổ sung làm phá hỏng sự tách bạch chi phí–tắc nghẽn khi liệt kê hết các đường đi. Một lời nhắc thứ ba yêu cầu chiến lược sạch hơn mang lại một khung hẹp hơn nhưng vẫn không có kết quả hoàn chỉnh.

Đó không phải là “bốn lời nhắc, xong.” Đó là nhiều giờ một mô hình đâm vào tường và nói thật về chúng. Bức tường cụ thể mà nó liên tục gặp, xuất hiện một đường đi bổ sung và phá hỏng sự tách bạch, chính là điều mà cấu trúc cuối cùng được tạo ra để ngăn chặn, bằng cách ghim mỗi đích vào đúng hai đường đi sao cho toàn bộ không gian định tuyến chỉ có tám lựa chọn mà bạn có thể tự liệt kê. Hãy ghi nhớ dạng thất bại đó. Bạn sắp tự mình gặp nó.

Lời nhắc thứ tư, được cho là gần với "chịu đủ thất bại rồi, vui lòng hoàn tất với một phản ví dụ đầy đủ, vô điều kiện," là lời nhắc tạo ra cấu trúc hoạt động, kèm theo chứng thư, một chương trình liệt kê, và đầy đủ LaTeX. Sự kiên nhẫn là quan trọng. Các lần từ chối trước đó cũng vậy; đó là những tự đánh giá trung thực.

Tự kiểm tra

Đây là nơi phần đưa tin của DataCamp có thể làm điều một bài tin tức không thể: để bạn tự chạy xác minh.

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

Thiết lập: ba đích, mỗi đích gửi 10 đơn vị, nên nhu cầu lớn nhất D là 10. Mỗi đích 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 bố trí sao cho mỗi cặp trong số chúng tranh nhau một tuyến cổ chai riêng, đường A dùng chung bởi đích 1 và 2, đường B bởi đích 1 và 3, đường C bởi đích 2 và 3. Trong luồng phân số, mỗi đích gửi 2/5 nhu cầu theo đường rẻ và 3/5 theo đường đắt, chi phí là 30 x 3/5 x 3 = 54. Khi đó mỗi tuyến chở phân số 4 + 4 = 8 đơn vị, và ngân sách tắc nghẽn là tải đó cộng D, tức 18.

Giờ hãy xem định tuyến không thể tách làm gì với điều đó. Hai đích cùng đi rẻ sẽ đổ 10 + 10 = 20 đơn vị lên tuyến dùng chung của họ, vượt ngân sách 18. Vậy nhiều nhất chỉ một đích có thể đi rẻ; hai đích còn lại trả 30 mỗi đích. Chi phí tối thiểu hợp lệ cho luồng không thể tách: 60. So với phân số 54. Có tám định tuyến tồn tại, nên ta chỉ việc kiểm hết thảy:

from itertools import product
	
# Three terminals, demand 10 each -> largest demand D = 10.
# Each has a cheap path (cost 0) and an expensive direct path (cost 30).
# Cheap paths pairwise share a PRIVATE bottleneck road, so every pair conflicts:
#   road A shared by {t1, t2},  road B by {t1, t3},  road C by {t2, t3}
# NOTE: this is a schematic instance to illustrate the check, not Rybin's graph.

demands = [10, 10, 10]
d_max = max(demands)          # congestion slack allowed on each road
cheap_frac = [2/5, 2/5, 2/5]  # expensive fraction is 3/5 each -> fractional cost 54
direct_cost = 30              # cost of one terminal's expensive path

# Which bottleneck roads each terminal's cheap path uses
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
]

# The fractional flow saturates each road, so its load is that road's capacity
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 units on each road

# Congestion rule: an unsplittable flow may exceed capacity by at most D
threshold = {road: cap[road] + d_max for road in cap}  # 18 on each road

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

print(f"Capacities (fractional load): {cap}")
print(f"Congestion budget per road  : {threshold}")
print(f"Fractional flow cost        : {fractional_cost}\n")
print(f"{'Route (0=cheap,1=exp)':22} {'Cost':>4} {'A':>3} {'B':>3} {'C':>3}  Valid")

valid_costs = []
for choices in product([0, 1], repeat=3):    # 0 = cheap, 1 = expensive
    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:                    # this terminal takes its cheap path
            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 "overload"
    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"\nMin valid unsplittable cost: {min(valid_costs)}")
print(f"Gap: {min(valid_costs) - fractional_cost} (counterexample if > 0)")

Chạy lên bạn sẽ được chi phí phân số là 54, chi phí tối thiểu hợp lệ của luồng không thể tách là 60, và khoảng cách là 6. Ba hàng bị quá tải chính là ba xung đột từng cặp; các định tuyến còn sống sót đều giữ nhiều nhất một đích đi rẻ.

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

Những điều còn bỏ ngỏ

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

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

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

Một phần của một mô thức

Câu chuyện này không phải là một dữ kiện đơn lẻ. Đây là giả thuyết thứ ba được cho là “ngã” nhờ sự trợ giúp của AI trong khoảng ba tháng, và mô thức đáng để ngẫm nghĩ.

Ngày 20 tháng 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, một bài toán 87 năm tuổi. Trước đó, vào tháng Năm, một mô hình của OpenAI được cho là đã bác bỏ giả thuyết khoảng cách đơn vị của Erdős 80 năm tuổi. Cùng tuần với tin này, một nghiên cứu sinh tiến sĩ ở Columbia dùng GPT-5.6 với một quy trình Codex có cấu trúc để giải sáu bài toán mở của Erdős trong năm ngày. Sợi chỉ đỏ xuyên suốt, như một nhà nghiên cứu nói, là các hệ thống này giỏi bác bỏ hơn chứng minh. Một phản ví dụ là một “nhân chứng” đơn lẻ bạn có thể kiểm; một chứng minh phải bao quát mọi trường hợp. Sự bất đối xứng đó dường như quyết định bài toán nào ngã trước.

Bài học thực tiễn không phải là “AI giải được toán.” Những gì chúng ta đang chứng kiến là AI hoạt động như một đối tác tìm kiếm kiên nhẫn, vét cạn theo tổ hợp: có thể liệt kê các họ tham số, giữ các dạng 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 kín. Đó là một năng lực cụ thể, hữu ích. Và nếu bạn muốn hiểu nơi nó có thể tấn công tiếp theo, câu hỏi cần hỏi không phải là giả thuyết nào lâu đời nhất, mà là giả thuyết nào có thể bị phá bởi một “nhân chứng” có thể kiểm duy nhất.