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 อย่างเนี้ยบและทำเหมือนเป็นของเขา สิ่งที่ทำได้คือยื่นอินสแตนซ์แบบสมบูรณ์ที่แสดงกลไกเดียวกัน ขนาดเล็กพอจะตรวจด้วยวิธีแรงดันได้ เพื่อจะได้เห็นกับตาว่า “เศษส่วนชนะทุกแบบแยกได้ที่ถูกกฎหมาย” หน้าตาเป็นอย่างไร 

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

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

บันทึกแชตที่ 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 ปี สัปดาห์เดียวกับข่าวนี้ นักศึกษาปริญญาเอกจาก Columbia ใช้ GPT-5.6 ร่วมกับเวิร์กโฟลว์ Codex แบบมีโครงสร้าง เพื่อแก้ปัญหาเปิดของ Erdős หกปัญหาในห้าวัน เส้นเรื่องร่วม ตามที่นักวิจัยคนหนึ่งว่าไว้ คือระบบเหล่านี้เก่งกว่าในการหักล้างมากกว่าพิสูจน์ ตัวอย่างหักล้างคือพยานเดี่ยวที่ตรวจได้ ส่วนบทพิสูจน์ต้องครอบคลุมทุกกรณี ความไม่สมมาตรนั้นดูจะเป็นตัวกำหนดว่าปัญหาไหนจะล้มก่อน

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