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 nhóm người nào đó 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, một bài toán mở trong tối ưu tổ hợp khoảng 30 năm. Bằng chứng ý tưởng là một đồ thị nhỏ. Chi phí luồng phân đoạn là 58, chi phí luồng không phân tách là 60. Hai điểm, ba thập kỷ, bốn lời nhắc.

Phần lớn bài viết chỉ lặp lại các con số mà không cho thấy cơ chế đằng sau, trong khi chính cơ chế mới là nơi chứa bài học thật sự. Đó cũng là nơi tôi cần nói thẳng với bạn về những gì đã được kiểm chứng và những gì thì chưa. Tóm tắt: các khái niệm là vững, tin tức vẫn là một tuyên bố chứ chưa phải định lý, và nếu bạn ngồi xuống để tái tạo chính xác đồ thị từ đầu, bạn sẽ hiểu vì sao những bài toán như thế này khó ngay khoảnh khắc bản 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ụ được cho là phản bác 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 nút đích giao hàng. Anh nói rằng định tuyến có thể phân tách (phân đoạn) tốn 58, trong khi bất kỳ định tuyến không phân 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 điểm đó, nếu qua được thẩm định hình thức, là đủ để đánh đổ giả thuyết.

Nó chưa qua bình duyệt đồng cấp. Rybin đã công bố toàn bộ cuộc trò chuyện ChatGPT để ai cũng có thể đọc cách xây dựng, và đã có 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ể lặp lại 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à câu chuyện của cả bài viết này.

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

Trước khi hiểu điều 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 đến ba thị trấn qua một mạng lưới đường bộ. Nếu bạn được phép chia nhỏ lô hàng, bạn có thể gửi nửa đơn theo một con đường và nửa còn lại theo con đường khác. Đó là định tuyến phân đoạn, khá 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ể chia nhỏ. Một đơn, một xe, một con đường, từ đầu đến cuối. Đó là luồng không phân 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 trăn trở từ năm 1999 rất dễ phát biểu. Nếu tồn tại một định tuyến phân đoạn rẻ, liệu bạn luôn có thể tìm được một định tuyến không phân tách mà cũng rẻ mà không làm quá tải đường sá quá mức 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 đó cực kỳ quan trọng, ta cần nói thật chính xác về nó.

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

Đây là khác 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 đoạn hợp lệ, bạn luôn có thể chuyển nó thành luồng không phân tách mà không vượt quá sức chứa của bất kỳ con đườ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ị đặt câu hỏi và chưa từng bị.

Điều Goemans riêng rẽ giả thuyết là phiên bản mạnh hơn, có xét chi phí: rằng cùng phép chuyển đổi đó có thể vừa kìm tổng chi phí xuống vừa kìm tắc nghẽn xuống. Tắc nghẽn và chi phí, cả hai bị chặn, trong một định tuyến. Định lý chỉ về tắc nghẽn thì an toàn. Giả thuyết về chi phí cộng tắc nghẽn là phần Rybin nói đã sụp. Nếu bạn chỉ mang đi một câu từ bài này, hãy là câu đó. Nhiều bài tường thuật hào hứng âm thầm đánh tráo hai điều, 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” chung, và ba nút đích, mỗi nút mang một nhu cầu. Mỗi đích có hai đường về: một đường trực tiếp đắt đỏ, hoặc một đường vòng miễn phí qua xương sống chung.

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

Tôi sẽ thành thật về một giới hạn ở đây. Tôi chưa thể tái tạo 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ừ một nguồn sơ cấp. Bản ghi của anh mô tả một điểm cụ thể trong một họ tham số, và 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 mà tôi đã kiểm chứng từng cạnh. Vì vậy tôi sẽ không dàn dựng một phép dẫn gọn gàng ra 58 và giả vờ đó là của anh. Điều tôi có thể làm là đưa bạn một trường hợp tự chứa cho thấy cùng cơ chế, đủ nhỏ để kiểm tra bằng vét cạn, để bạn tự thấy “phân đoạn vượt mọi không phân 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 ít thú vị nhất của câu chuyện này, dù đó là phần lan truyền.

Bản chat Rybin chia sẻ cho thấy mô hình thất bại trước, và thất bại một cách chuẩn 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 trắng, nói thẳng rằng 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ó triển vọng đều nảy sinh một tùy chọn định tuyến ẩn bổ sung phá hủy sự tách bạch chi phí–tắc nghẽn khi liệt kê hết các đường đi. Lời nhắc thứ ba yêu cầu một chiến lược gọn hơn đưa tớ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. Cái tường cụ thể mà nó cứ đâm vào, một đường đi bổ sung xuất hiện và phá hỏng sự tách bạch, chính là điều mà cấu trúc cuối cùng được thiết kế để ngăn, bằng cách cố định 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 bạn có thể liệt kê thủ công. Hãy ghi nhớ kiểu lỗi đó. Bạn sắp gặp nó.

Lời nhắc thứ tư, được cho là gần với “chán nản với thất bại của bạn rồi, vui lòng hoàn thành với một phản ví dụ hoàn chỉnh, vô điều kiện,” là lời nhắc tạo ra cấu trúc hoạt động, kèm chứng chỉ chứng minh, một chương trình liệt kê, và bản LaTeX đầy đủ. Sự kiên nhẫn là quan trọng. Những 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à chỗ trang DataCamp có thể làm điều mà một bài tin tức không thể: để bạn tự chạy kiểm chứng.

Một lưu ý nhanh trước phần mã. Những gì sau đây không phải là đồ thị của Rybin. Đây là một trường hợp sơ đồ tôi dựng một cách trung thực, trong đó mỗi đích thực sự chỉ có đúng hai đường đi, số học khép kín, và khoảng cách là 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. Bản thân nó không bác bỏ điều gì, và tôi sẽ giải thích tại sao ngay sau khi bạn chạy nó.

Thiết lập: ba đích, mỗi đích vận chuyển 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 sắp sao cho mỗi cặp trong số chúng tranh nhau một con đường nút cổ chai riêng, đường A chia sẻ 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 đoạn, 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. Mỗi con đường khi đó mang 4 + 4 = 8 đơn vị theo phân đoạn, 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 phân tách làm gì với điều đó. Hai đích cùng đi rẻ sẽ đổ 10 + 10 = 20 đơn vị lên con đường chung của họ, vượt ngân sách 18. Vậy nhiều nhất một đích có thể đi rẻ; hai đích còn lại trả 30 mỗi đích. Chi phí không phân tách hợp lệ tối thiểu: 60. So với phân đoạn 54. Có tám cách định tuyến, nên ta chỉ việc kiểm tra tất cả:

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 đoạn 54, chi phí không phân tách hợp lệ tối thiểu 60, và một khoảng cách 6. Ba hàng bị quá tải là ba xung đột từng cặp; những định tuyến còn lại đều giữ nhiều nhất một đích đi rẻ.

Vậy 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 đường đi và không hơn. Xây đồ thị này từ các con đường và nút thực, một đường rẻ thứ tư có xu hướng xuất hiện từ tổ hợp. Một đích tìm thấy con đường thứ ba về nhà vừa rẻ vừa ở trong ngân sách, và khoảng cách biến mất. Đường bổ sung đó chính là lỗi mà mô hình báo cáo ở ba lần thử đầu. Một “đồ gá” sạch sẽ, đối xứng phá một giả thuyết 30 năm chỉ bằng 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à đúng và thuộc tính mục tiêu là có thật. Còn liệu một đồ thị nhất định có thật sự mang thuộc tính đó, không rò rỉ, mới là phần khó, và đó là lý do trường hợp thật của Rybin là một điểm được tinh chỉnh trong một họ tham số thay vì một tam giác gọn gàng.

Những gì 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ách xây dựng; cả hai đều chưa qua quy trình phản biện để 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 tái dựng độc lập từ một nguồn sơ cấp mà tôi tìm thấy. Các con số đang lưu truyền đến từ bài đăng của anh và bản ghi chia sẻ. Vài nhà nghiên cứu đã kiểm tra số học của anh và gọi 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 sẽ khiến kết quả 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 cộng đồng phi chính thức, không phải báo cáo phản biện. Hãy coi 58 so với 60 như một tuyên bố có cơ sở tốt, không phải một sự thật đã ngã ngũ.

Định lý 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ô thức

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

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 5, 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 quy trình 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. 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 phản chứng hơn là chứng minh. Một phản ví dụ là một nhân chứng đơn lẻ bạn có thể kiểm tra; 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 sụp đổ trước.

Thông điệp thực tiễn không phải là “AI giải toán.” Những gì ta đang chứng kiến là AI làm đố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. Đó là một năng lực cụ thể, hữu dụng. Và nếu bạn muốn hiểu nó sẽ tác động ở đâu tiếp theo, câu 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á vỡ bởi một nhân chứng đơn lẻ có thể kiểm tra.