GPT-5.6 และสมมติฐาน Dinitz-Garg-Goemans

เมื่อวันที่ 22 กรกฎาคม 2026 Dmitry Rybin โพสต์ข้ออ้างบน X ที่ทำให้คนบางประเภทวางแก้วกาแฟลง: GPT-5.6 Pro สร้างตัวอย่างโต้แย้งสมมติฐาน Dinitz-Garg-Goemans ซึ่งเป็นปัญหาเปิดในด้านการเพิ่มประสิทธิภาพเชิงสัณฐานวิทยามานานราว 30 ปี หลักฐานแนวคิดคือกราฟเล็กๆ กราฟหนึ่ง ค่าใช้จ่ายของโฟลว์แบบเศษส่วน 58 ค่าใช้จ่ายของโฟลว์แบบไม่แบ่งส่วน 60 สองแต้ม สามทศวรรษ สี่พรอมป์ต์

บทความส่วนใหญ่ย้ำแต่ตัวเลขโดยไม่แสดงกลไกเบื้องหลัง ทั้งที่บทเรียนสำคัญอยู่ตรงกลไกนั่นเอง และตรงนั้นแหละที่ต้องพูดกันตรงๆ ว่าอะไรได้รับการยืนยันแล้วและอะไรยังไม่ได้ ฉบับย่อ: แนวคิดแข็งแรง ข่าวนี้คือข้ออ้างยังไม่ใช่ทฤษฎีบท และถ้านั่งทำกราฟเดียวกันขึ้นใหม่ตั้งแต่ศูนย์ จะเข้าใจทันทีว่าทำไมปัญหาแบบนี้ถึงยาก เมื่อการประกอบชิ้นงานของคุณเริ่ม “รั่ว”

คำตอบฉับไว

Rybin รายงานว่า GPT-5.6 Pro ที่ถูกชี้นำด้วยพรอมป์ต์สี่อันรวมกันไม่ถึง 60 คำ ได้สร้างตัวอย่างโต้แย้งต่อสมมติฐานด้านต้นทุนของ Goemans ซึ่งเป็นปัญหาเปิดมาตั้งแต่ราวปี 1999 อินสแตนซ์ของเขาเป็นกราฟมีทิศทางขนาดเล็ก มีต้นทางเดียวและมีปลายทางส่งของสามจุด เขาระบุว่าเส้นทางแบบแยกส่วน (เศษส่วน) มีค่าใช้จ่าย 58 ขณะที่เส้นทางแบบไม่แบ่งส่วนใดๆ ที่รักษาความหนาแน่นการจราจรให้อยู่ในงบประมาณที่ยอมรับได้ จะมีค่าใช้จ่ายอย่างน้อย 60 ช่องว่างสองแต้มนี้ หากผ่านการทบทวนอย่างเป็นทางการ ก็เพียงพอจะล้มสมมติฐานดังกล่าว

ยังไม่ผ่านการพิจารณาตีพิมพ์โดยผู้ทรงคุณวุฒิ Rybin เผยแพร่บทสนทนากับ ChatGPT ฉบับเต็มเพื่อให้ใครๆ อ่านขั้นตอนการสร้างได้ และมีหลายคนตรวจสอบเลขคณิตของเขาแล้วพบว่าสอดคล้องกัน อย่างไรก็ดี การคำนวณที่ทำซ้ำได้กับบทพิสูจน์ที่ยอมรับได้นั้นเป็นคนละเรื่อง และช่องว่างระหว่างทั้งสองก็คือแก่นของบทความนี้

สมมติฐาน Dinitz-Garg-Goemans คืออะไร?

ก่อนจะซาบซึ้งว่าอะไรล้มลง หรืออาจจะล้ม เราต้องเข้าใจให้ชัดว่าสมมติฐานพูดว่าอะไรแน่

ลองนึกภาพคลังสินค้าที่กำลังส่งออเดอร์ไปยังสามเมืองผ่านเครือข่ายถนน หากอนุญาตให้แยกชิ้นส่งได้ ก็สามารถส่งครึ่งหนึ่งไปถนนเส้นหนึ่ง อีกครึ่งไปอีกเส้นหนึ่ง นั่นคือการจัดเส้นทางแบบเศษส่วน ซึ่งยืดหยุ่นและมักจะหาชุดเส้นทางที่ถูกกว่าได้ แต่ของจริงจำนวนมากแยกไม่ได้ ออเดอร์เดียว รถคันเดียว ถนนเส้นเดียว ตั้งแต่ต้นจนจบ นั่นคือโฟลว์แบบไม่แบ่งส่วน และเป็นสิ่งที่ออเดอร์ขนส่ง แพ็กเก็ตเครือข่าย หรือคอนเทนเนอร์ต้องทำจริง

คำถามที่ผู้คนขบคิดมาตั้งแต่ปี 1999 กล่าวได้ง่ายๆ ว่า หากมีเส้นทางแบบแยกส่วนที่ถูกอยู่แล้ว จะสามารถหาเส้นทางแบบไม่แบ่งส่วนที่ก็ถูกได้เสมอ โดยไม่ทำให้ถนนต่างๆ แบกรับเกินไปหรือไม่?

Yefim Dinitz, Naveen Garg และ Michel Goemans ปิดครึ่งหนึ่งของปัญหานี้ได้ ส่วนอีกครึ่งหนึ่งคือสิ่งที่ GPT-5.6 เข้าไปโจมตี เพื่อเข้าใจว่าความแตกต่างนี้สำคัญอย่างยิ่งเพียงใด เราต้องระบุให้แม่นยำ

ทฤษฎีบท vs. สมมติฐาน

นี่คือความแตกต่างที่บทความจำนวนมากทำให้พร่ามัว ฉันจะระบุให้ชัดเจนเพียงครั้งเดียว แล้วใช้ความแตกต่างนี้ตลอดบทความ

Dinitz, Garg และ Goemans พิสูจน์ ผลเกี่ยวกับความหนาแน่น: เมื่อมีโฟลว์แบบเศษส่วนที่ถูกต้อง คุณสามารถแปลงมันเป็นโฟลว์แบบไม่แบ่งส่วนได้เสมอ โดยจะไม่ทำให้ความจุของถนนเส้นใดเกินได้มากไปกว่าความต้องการที่ใหญ่ที่สุดเพียงรายการเดียว ให้เรียกค่านั้นว่า D ทฤษฎีบทนี้ไม่ถูกตั้งคำถาม และไม่เคยถูกตั้งคำถาม

สิ่งที่ Goemans แยกต่างหากได้คาดคะเนไว้ คือเวอร์ชันที่แข็งแรงกว่าและรับรู้ต้นทุน: ว่าการแปลงเดียวกันนี้สามารถกดต้นทุนรวมให้ต่ำ พร้อมๆ กับกดความหนาแน่นให้ต่ำได้ ทั้งความหนาแน่นและต้นทุนถูกคุมให้อยู่ในเส้นทางเดียว ทฤษฎีบทที่ว่าด้วยความหนาแน่นเพียงอย่างเดียวยังคงปลอดภัย ส่วนสมมติฐานเรื่อง “ต้นทุนบวกความหนาแน่น” คือชิ้นส่วนที่ Rybin ระบุว่าล้มลง หากจะจำเพียงประโยคเดียวจากบทความนี้ จงจำประโยคนั้น ข่าวตื่นเต้นจำนวนมากสลับสองประเด็นนี้อย่างเงียบๆ และความต่างระหว่างทั้งสองก็คือช่องว่างทางคณิตศาสตร์ทั้งหมดที่ใช้เวลา 30 ปีในการปิด

GPT-5.6 สร้างอะไรขึ้นมาจริงๆ

อินสแตนซ์ของ Rybin เล็กพอจะอธิบายในย่อหน้าเดียว มีต้นทาง โหนดกลางไม่กี่จุดที่รวมกันเป็น “กระดูกสันหลัง” ร่วม และปลายทางสามจุด แต่ละจุดมีความต้องการบรรทุก แต่ละปลายทางมีทางกลับบ้านสองทาง: ทางตรงที่แพง หรือทางอ้อมฟรีผ่านกระดูกสันหลังร่วม

ความตึงเครียดเป็นเชิงโครงสร้าง ทางอ้อมที่ถูกแย่งพื้นที่บนกระดูกสันหลังร่วม หากมีปลายทางมากเกินไปพยายามใช้เส้นทางถูกพร้อมกัน ถนนบนกระดูกสันหลังจะล้น ดันไปไกลพอแล้วจะเหลือแค่ปลายทางเดียวที่ใช้เส้นทางถูกได้ในโฟลว์แบบไม่แบ่งส่วนที่ถูกต้อง ส่วนที่เหลือต้องถูกบังคับให้ใช้เส้นทางตรงที่แพง และต้นทุนก็สูงขึ้น โฟลว์แบบเศษส่วนที่แบ่งได้จะกระจายความต้องการไปทั้งสองเส้นทาง และลอดใต้ความจุทุกเส้นพร้อมกัน นั่นคือวิธีที่ทำให้ต้นทุนแบบเศษส่วนต่ำกว่าต้นทุนแบบไม่แบ่งส่วนที่ถูกกฎหมายที่ถูกที่สุด ตัวเลขของ Rybin สำหรับอินสแตนซ์ของเขาคือ 58 และ 60

ขอพูดตรงๆ ถึงข้อจำกัดข้อหนึ่ง ฉันยังไม่สามารถสร้างกราฟของ Rybin แบบเป๊ะๆ คือความจุที่เจาะจงและความขัดแย้งเป็นคู่ๆ จากแหล่งปฐมภูมิได้ บันทึกบทสนทนาของเขาอธิบายจุดๆ หนึ่งในครอบครัวพารามิเตอร์ และคำอธิบาย “เจ็ดโหนด” ที่แพร่หลายคือภาพย่อ ไม่ใช่โครงสร้างที่ฉันตรวจสอบทีละเส้นเชื่อมแล้ว ดังนั้นฉันจะไม่จัดเวทีให้มีการสรุปเลข 58 อย่างสวยงามแล้วทำเหมือนเป็นของเขา สิ่งที่ฉันทำได้คือส่งอินสแตนซ์แบบปิดจบให้คุณ ซึ่งแสดงกลไกแบบเดียวกัน ขนาดเล็กพอจะตรวจด้วยวิธี brute force เพื่อให้คุณเห็นกับตาว่า “โฟลว์แบบเศษส่วนชนะทุกโฟลว์แบบไม่แบ่งส่วนที่ถูกกฎหมาย” เป็นอย่างไร 

สี่พรอมป์ต์ หลายชั่วโมง

จำนวนพรอมป์ต์เป็นส่วนที่น่าสนน้อยที่สุดของเรื่องนี้ ถึงอย่างนั้นก็เป็นส่วนที่กลายเป็นไวรัล

บันทึกแชตที่ Rybin แชร์แสดงให้เห็นว่าโมเดลล้มเหลวในตอนแรก และล้มเหลวอย่างซื่อสัตย์ พรอมป์ต์เปิดขอให้หาโครงสร้างตัวอย่างโต้แย้ง มันทำงานนานเกือบชั่วโมงและกลับมามือเปล่า ระบุโต้งๆ ว่าการนำเสนอสิ่งที่มีอยู่ว่าเป็นตัวอย่างโต้แย้งที่ถูกต้องนั้นเป็นเท็จ

เมื่อถูกขอให้ทำต่อ มันก็รันอีก และรายงานว่าไม่มีอะไรอีก โดยอธิบายว่าทำไมโครงสร้างที่ดูมีหวังแต่ละอันจึงโผล่เส้นทางเพิ่มเติมที่ซ่อนอยู่ ซึ่งทำลายการแยกต้นทุน-ความหนาแน่นเมื่อไล่เส้นทางทั้งหมดครบแล้ว พรอมป์ต์ที่สามที่ขอให้วางกลยุทธ์ที่สะอาดขึ้น ได้กรอบที่แคบลงแต่ก็ยังไม่มีผลลัพธ์สำเร็จ

นั่นไม่ใช่ “สี่พรอมป์ต์ จบ” แต่มันคือชั่วโมงๆ ที่โมเดลชนกำแพงและบอกความจริงเกี่ยวกับมัน กำแพงเฉพาะที่มันชนซ้ำๆ คือมีเส้นทางพิเศษโผล่มาและทำลายการแยก และนั่นเองคือสิ่งที่โครงสร้างสุดท้ายถูกออกแบบมาเพื่อป้องกัน โดยตรึงแต่ละปลายทางให้มีเพียงสองเส้นทางพอดี ทำให้พื้นที่การจัดเส้นทางทั้งหมดมีแปดทางเลือกที่คุณไล่ตรวจได้ด้วยมือ โปรดจำโหมดความล้มเหลวนั้นไว้ คุณกำลังจะเจอมันด้วยตัวเอง

พรอมป์ต์ที่สี่ ซึ่งรายงานว่ามีบางอย่างคล้าย“พอแล้วกับความล้มเหลวของคุณ กรุณาจบด้วยตัวอย่างโต้แย้งที่สมบูรณ์และไม่มีเงื่อนไข” คือพรอมป์ต์ที่ให้โครงสร้างที่ใช้การได้ พร้อมใบรับรองพิสูจน์ โปรแกรมไล่ลิสต์ และ LaTeX ครบถ้วน ความอดทนมีความหมาย และการปฏิเสธก่อนหน้านั้นก็สำคัญ—มันเป็นการประเมินตนเองอย่างซื่อสัตย์

ตรวจเองกับมือ

ตรงนี้คือสิ่งที่บทความของ DataCamp ทำได้มากกว่าข่าวทั่วไป: ให้คุณรันการตรวจสอบได้เอง

ข้อควรระวังก่อนดูโค้ด สิ่งที่จะตามมาไม่ใช่กราฟของ Rybin มันเป็นอินสแตนซ์แบบแผนภาพที่ฉันสร้างขึ้นอย่างตรงไปตรงมา โดยแต่ละปลายทางมีสองเส้นทางจริงๆ เลขคณิตปิด และช่องว่างมีอยู่จริง มันแสดงรูปทรงของตัวอย่างโต้แย้งประเภทนี้และเทคนิคในการตรวจสอบ แต่มันไม่ได้ล้มล้างอะไรด้วยตัวมันเอง และฉันจะอธิบายว่าทำไมทันทีหลังจากที่คุณรันมัน

การตั้งค่า: มีปลายทางสามจุด แต่ละจุดส่ง 10 หน่วย ดังนั้นความต้องการที่ใหญ่ที่สุด D คือ 10 แต่ละจุดมีทางตรงที่แพง (ต้นทุน 30) และทางถูกที่ฟรี เส้นทางถูกถูกจัดให้ทุกคู่ของมันแย่งถนนคอขวดส่วนตัว ถนน A ใช้ร่วมกันโดยปลายทาง 1 และ 2 ถนน B โดย 1 และ 3 ถนน C โดย 2 และ 3 ในโฟลว์แบบเศษส่วน แต่ละปลายทางจะส่ง 2/5 ของความต้องการผ่านทางถูก และ 3/5 ทางแพง ทำให้ต้นทุนเป็น 30 x 3/5 x 3 = 54 จากนั้นถนนแต่ละเส้นจะรับโหลดเศษส่วน 4 + 4 = 8 หน่วย และงบประมาณความหนาแน่นคือโหลดนั้นบวก D รวมเป็น 18

ตอนนี้ดูว่าโฟลว์แบบไม่แบ่งส่วนทำอะไรกับสิ่งนั้น สองปลายทางที่ไปทางถูกทั้งคู่จะทุ่ม 10 + 10 = 20 หน่วยลงบนถนนที่ใช้ร่วมกัน เกินงบ 18 ดังนั้นอย่างมากก็มีเพียงปลายทางเดียวที่สามารถใช้ทางถูก อีกสองปลายทางต้องจ่าย 30 คนละเส้น ต้นทุนขั้นต่ำของโฟลว์แบบไม่แบ่งส่วนที่ถูกต้อง: 60 เทียบกับแบบเศษส่วน 54 มีเส้นทางเลือกทั้งหมดแปดแบบ เราจึงไล่ตรวจทุกแบบ:

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)")

รันแล้วจะได้ต้นทุนแบบเศษส่วน 54 ต้นทุนแบบไม่แบ่งส่วนขั้นต่ำที่ถูกต้อง 60 และช่องว่าง 6 แถวที่ล้นสามแถวคือความขัดแย้งแบบจับคู่สามกรณี เส้นทางเดียวที่ผ่านจะคุมให้มีปลายทางถูกไม่เกินหนึ่งจุด

ดังนั้นสมมติฐานตายแล้วหรือ? ยังไม่ใช่ และนี่คือส่วนที่สัญญาว่าจะอธิบาย การไล่ลิสต์แปดบรรทัดนั้นบอกความจริงได้ก็ต่อเมื่อแต่ละปลายทางมีจริงๆ แค่สองเส้นทางและไม่มากกว่านั้น ลองสร้างกราฟนี้จากถนนและโหนดจริงๆ แล้วมักจะเกิดเส้นทางถูกที่สี่ขึ้นมาจากคอมบิเนทอริกส์ ปลายทางจะหาเส้นทางกลับบ้านแบบถูกทางที่สามซึ่งยังอยู่ใต้เพดานงบ และช่องว่างก็หายไป เส้นทางพิเศษนี่แหละคือความล้มเหลวที่โมเดลรายงานไว้ในสามครั้งแรก แก็ดเจ็ตที่สะอาดและสมมาตรซึ่งทำลายสมมติฐาน 30 ปีได้ใน Python แปดบรรทัดนั้นมันดีเกินจริง และก็เป็นเช่นนั้น โค้ดข้างบนพิสูจน์ว่าวิธีตรวจนั้นถูกต้องและคุณสมบัติเป้าหมายมีอยู่จริง ว่ากราฟใดกราฟหนึ่งมีคุณสมบัตินั้นจริงโดยไม่มีรูรั่วหรือไม่ นั่นคือส่วนที่ยาก และเป็นเหตุผลที่อินสแตนซ์จริงของ Rybin เป็นจุดที่ปรับจูนในครอบครัวพารามิเตอร์ ไม่ใช่สามเหลี่ยมสวยๆ

อะไรยังไม่ยุติ

ยังไม่มีบทความทางการปรากฏ Rybin แชร์บทสนทนาและโครงสร้าง แต่ทั้งสองยังไม่ผ่านกระบวนการผู้ทรงคุณวุฒิที่จะทำให้ชุมชนคณิตศาสตร์ปิดสมมติฐานนี้อย่างเป็นทางการได้

กราฟที่ตีพิมพ์แบบเป๊ะๆ ยังไม่ถูกประกอบขึ้นใหม่อย่างอิสระจากแหล่งปฐมภูมิที่ฉันหาได้ ตัวเลขที่หมุนเวียนมาจากโพสต์และบันทึกบทสนทนาที่แชร์ มีนักวิจัยหลายคนตรวจเลขคณิตของเขาและบอกว่าสอดคล้อง และมีคนหนึ่งแสดงว่าอินสแตนซ์ของเขาอยู่ในครอบครัวสามพารามิเตอร์อนันต์บนโหนดเดียวกัน ซึ่งจะทำให้ผลน่าสนใจกว่าความบังเอิญครั้งเดียว เป็นสัญญาณที่ดี แต่ก็เป็นการตรวจแบบไม่เป็นทางการของชุมชน ไม่ใช่รายงานผู้ทรงคุณวุฒิ จงมอง 58 เทียบ 60 ว่าเป็นข้ออ้างที่มีหลักฐานหนุนหลังดี ไม่ใช่ข้อเท็จจริงที่ยุติแล้ว

ทฤษฎีบทความหนาแน่นปี 1999 ไม่ได้รับผลกระทบจากเรื่องนี้เลย

ส่วนหนึ่งของรูปแบบ

เรื่องนี้ไม่ใช่ข้อมูลจุดเดียว นี่คือสมมติฐานลำดับที่สามที่มีรายงานว่าล้มด้วยความช่วยเหลือของ AI ในราวสามเดือน และรูปแบบนี้น่าคิด

เมื่อวันที่ 20 กรกฎาคม มีรายงานว่า Claude Fable 5 ช่วยนักคณิตศาสตร์ Levent Alpöge หาตัวอย่างโต้แย้งต่อสมมติฐาน Jacobian ซึ่งเป็นปัญหาอายุ 87 ปี ก่อนหน้านั้นในเดือนพฤษภาคม มีรายงานว่าโมเดลของ OpenAI ล้มสมมติฐานระยะทางหนึ่งหน่วยของ Erdős อายุ 80 ปี สัปดาห์เดียวกับข่าวนี้ นักศึกษาปริญญาเอกจากโคลัมเบียใช้ GPT-5.6 กับเวิร์กโฟลว์ Codex แบบมีโครงสร้างเพื่อแก้ปัญหาเปิดของ Erdős หกข้อในห้าวัน เส้นเรื่องร่วม ตามที่นักวิจัยคนหนึ่งว่าไว้ คือระบบเหล่านี้ถนัดการล้มข้อคาดคะเนมากกว่าการพิสูจน์ ตัวอย่างโต้แย้งคือตัวพยานเดี่ยวที่ตรวจได้ ส่วนบทพิสูจน์ต้องครอบคลุมทุกกรณี ความไม่สมมาตรนี้ดูเหมือนจะเป็นตัวตัดสินว่าปัญหาไหนจะล้มก่อน

ข้อสรุปเชิงปฏิบัติไม่ใช่ “AI แก้คณิตศาสตร์” สิ่งที่เราเห็นคือ AI ทำงานเป็นคู่คิดที่อดทนและไล่ค้นหาเชิงคอมบิเนทอริกส์ได้อย่างครอบคลุม: ที่สามารถไล่ลิสต์ครอบครัวพารามิเตอร์ จดจำโหมดความล้มเหลวไว้ในหน่วยความจำการทำงานข้ามความพยายามหลายครั้ง และบอกความจริงเมื่อโครงสร้างยังปิดไม่สนิท นั่นคือความสามารถเฉพาะที่มีประโยชน์ และหากอยากเข้าใจว่ามันจะเล่นงานอะไรต่อไป คำถามที่ควรถามไม่ใช่ว่าสมมติฐานใดเก่าแก่ที่สุด แต่คือสมมติฐานใดที่สามารถถูกทำลายได้ด้วยพยานเดี่ยวที่ตรวจสอบได้