GPT-5.6 और Dinitz-Garg-Goemans प्रतिज्ञप्ति

22 जुलाई, 2026 को, Dmitry Rybin ने X पर एक दावा किया जिससे एक खास तरह के लोग अपनी कॉफी नीचे रखकर बैठ गए: GPT-5.6 Pro ने Dinitz-Garg-Goemans प्रतिज्ञप्ति का एक प्रतिवाद उदाहरण तैयार किया, जो लगभग 30 वर्षों से संयोज्य अनुकूलन में खुला था। अवधारणा का प्रमाण एक छोटा-सा ग्राफ था। आंशिक (fractional) प्रवाह लागत 58, अविभाज्य (unsplittable) प्रवाह लागत 60। दो अंक, तीन दशक, चार प्रॉम्प्ट।

अधिकांश कवरेज इन संख्याओं को दोहराते हैं पर उनके पीछे की कार्य-विधि नहीं दिखाते, और वही कार्य-विधि असली सीख समेटे है। यहीं मुझे यह भी साफ करना है कि किस हिस्से का सत्यापन हुआ है और किसका नहीं। संक्षेप में: अवधारणाएँ ठोस हैं, खबर एक दावा है—थियोरम अभी नहीं—और यदि आप बैठकर पूरा वही ग्राफ शून्य से फिर बनाते हैं, तो जैसे ही आपके पुनर्निर्माण में कहीं से रिसाव होता है, आप समझ जाते हैं कि ऐसे सवाल कठिन क्यों होते हैं।

संक्षेप में उत्तर

Rybin बताता है कि GPT-5.6 Pro ने, कुल 60 शब्दों से कम के चार प्रॉम्प्ट के दिशा-निर्देशन में, Goemans की लागत-संबंधी प्रतिज्ञप्ति के लिए एक कथित प्रतिवाद उदाहरण दिया—एक समस्या जो लगभग 1999 से खुली थी। उसका उदाहरण एक छोटा निर्देशित ग्राफ है, जिसमें एक स्रोत और तीन डिलीवरी टर्मिनल हैं। वह बताता है कि विभाज्य (fractional) रूटिंग की लागत 58 है, जबकि कोई भी अविभाज्य रूटिंग जो भीड़भाड़ (congestion) को निर्धारित बजट में रखे, उसकी लागत कम-से-कम 60 है। यह दो अंकों का अंतर, यदि औपचारिक समीक्षा में टिकता है, तो प्रतिज्ञप्ति को डुबाने के लिए पर्याप्त है।

इसका सहकर्मी-समीक्षण नहीं हुआ है। Rybin ने पूरा ChatGPT संवाद प्रकाशित किया है ताकि कोई भी निर्माण पढ़ सके, और कई लोगों ने उसकी गणना जाँची है और उसे सुसंगत पाया है। पर दोहराई जा सकने वाली गणित और स्वीकृत प्रमाण अलग चीजें हैं, और उनके बीच की दूरी ही इस लेख की पूरी कहानी है।

Dinitz-Garg-Goemans प्रतिज्ञप्ति क्या है?

यह समझने से पहले कि क्या गिरा—या शायद गिरा—हमें यह समझना होगा कि प्रतिज्ञप्ति असल में कहती क्या है।

एक गोदाम की कल्पना करें जो सड़कों के नेटवर्क के जरिए तीन कस्बों को ऑर्डर भेजता है। यदि आपको एक खेप को बाँटने की अनुमति है, तो आप आधा ऑर्डर एक सड़क से और आधा दूसरी से भेज सकते हैं। यह आंशिक (fractional) रूटिंग है, और यह लचीली होती है; आमतौर पर यह सस्ते रास्तों का सेट ढूँढ लेती है। पर वास्तविक माल का बड़ा हिस्सा बाँटा नहीं जा सकता। एक ऑर्डर, एक ट्रक, एक सड़क, शुरू से अंत तक। यह अविभाज्य प्रवाह है, और वास्तविक जीवन में माल-ढुलाई, नेटवर्क पैकेट, या शिपिंग कंटेनर को यही करना पड़ता है।

1999 से जिस सवाल को लोग चबा रहे हैं, वह कहना सरल है। यदि कोई सस्ती विभाज्य रूटिंग मौजूद है, तो क्या आप हमेशा ऐसी अविभाज्य रूटिंग पा सकते हैं जो भी सस्ती हो और सड़कों पर बहुत ज्यादा लोड न डाले?

Yefim Dinitz, Naveen Garg, और Michel Goemans ने इसका आधा हिस्सा सुलझाया। दूसरा आधा वही है जिस पर GPT-5.6 ने निशाना साधा। यह फर्क क्यों बहुत मायने रखता है, यह समझने के लिए हमें सटीक होना होगा।

थियोरम बनाम प्रतिज्ञप्ति

यही वह फर्क है जिसे अधिकतर लेख धुंधला कर देते हैं, तो मैं इसे एक बार ठीक-ठीक कह दूँगा और शेष लेख में इसी पर भरोसा करूँगा।

Dinitz, Garg, और Goemans ने भीड़भाड़ (congestion) पर एक परिणाम साबित किया: किसी वैध आंशिक प्रवाह के दिए जाने पर, आप उसे हमेशा एक अविभाज्य प्रवाह में बदल सकते हैं बिना किसी सड़क की क्षमता को सबसे बड़े माँग, उसे D कहें, से अधिक पार किए। यह थियोरम संदेह के दायरे में नहीं है और कभी था भी नहीं।

जो Goemans ने अलग से अनुमान लगाया था, वह अधिक प्रबल, लागत-सचेत संस्करण है: कि वही रूपांतरण कुल लागत को भी नीचे रख सके, साथ ही भीड़भाड़ को भी नियंत्रित रखे। एक ही रूटिंग में भीड़भाड़ और लागत—दोनों बाधित। केवल भीड़भाड़ वाला थियोरम सुरक्षित है। लागत-प्लस-भीड़भाड़ वाली प्रतिज्ञप्ति वही हिस्सा है जिसे Rybin कहता है कि गिर गया। यदि आप इस लेख से एक वाक्य याद रखें, तो वही रहे। कई उत्साहित रिपोर्टें चुपचाप दोनों को अदला-बदली कर देती हैं, और उनके बीच का फर्क ही वह पूरा गणितीय अंतर है जिसे बंद करने में 30 साल लगे।

GPT-5.6 ने वास्तव में क्या बनाया

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-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 का अंतर मिलता है। जो तीन पंक्तियाँ ओवरलोड हैं, वे तीन जोड़ी-दर-जोड़ी टकराव हैं; जो रूटिंग बचती हैं, वे अधिकतम एक टर्मिनल को ही सस्ता रखती हैं।

तो क्या प्रतिज्ञप्ति खत्म? अभी नहीं, और यही वह हिस्सा है जिसका मैंने वादा किया था। वह आठ-पंक्ति गिनती तभी सच बोलती है जब हर टर्मिनल के पास सच में केवल दो ही रास्ते हों—और कोई नहीं। इस ग्राफ को असली सड़कों और नोड से बनाइए, तो संयोज्य गणित से आम तौर पर चौथा सस्ता रास्ता उभर आता है। कोई टर्मिनल घर पहुँचने का तीसरा सस्ता और बजट के भीतर रास्ता खोज निकालता है, और अंतर मिट जाता है। वही अतिरिक्त रास्ता ठीक वही विफलता है जिसे मॉडल ने अपनी पहली तीन कोशिशों में रिपोर्ट किया। एक साफ, सममित गैजेट जो आठ पंक्तियों के Python में 30 साल पुरानी प्रतिज्ञप्ति तोड़ दे—वह सच होने के लिए बहुत अच्छा लगता है, और है भी। ऊपर का कोड यह साबित करता है कि जाँच ठोस है और लक्ष्य-गुण वास्तविक है। किसी दिए गए ग्राफ में वह गुण बिना किसी रिसाव के है या नहीं—यही कठिन हिस्सा है, और यही वजह है कि Rybin का वास्तविक उदाहरण एक पैरामीटर परिवार का ठीक-ठीक चुना गया बिंदु है, कोई सुथरा त्रिभुज नहीं।

क्या अब भी अनसुलझा है

कोई औपचारिक शोध-पत्र सामने नहीं आया है। Rybin ने संवाद और निर्माण साझा किया; दोनों से होकर वह रेफरी प्रक्रिया नहीं गुज़री जिससे गणितीय समुदाय प्रतिज्ञप्ति को आधिकारिक तौर पर बंद माने।

मुझे जो प्राथमिक स्रोत मिला हो, उससे ठीक वही प्रकाशित ग्राफ स्वतंत्र रूप से फिर से नहीं बनाया गया। जो संख्याएँ घूम रही हैं वे उसके पोस्ट और साझा ट्रांसक्रिप्ट से आती हैं। कई शोधकर्ताओं ने उसकी गणना जाँची है और उसे सुसंगत कहा है, और एक ने दिखाया कि उसका उदाहरण उन्हीं नोड पर एक अनंत तीन-पैरामीटर परिवार के भीतर बैठता है—जो नतीजे को एक अकेले सौभाग्यशाली संयोग से अधिक समृद्ध बनाता है। यह उत्साहजनक है, पर यह सामुदायिक अनौपचारिक जाँच है, रेफरी रिपोर्ट नहीं। 58-और-60 को एक अच्छे समर्थन वाला दावा समझिए, पक्का तथ्य नहीं।

1999 का भीड़भाड़ वाला थियोरम इससे अप्रभावित है।

एक पैटर्न का हिस्सा

यह कहानी एक अकेला डेटा-पॉइंट नहीं है। यह लगभग तीन महीनों में AI-सहायता से गिरने की रिपोर्ट वाली तीसरी प्रतिज्ञप्ति है, और यह पैटर्न गौर करने लायक है।

20 जुलाई को, Claude Fable 5 ने गणितज्ञ Levent Alpöge को Jacobian प्रतिज्ञप्ति का एक प्रतिवाद उदाहरण ढूँढने में मदद की बताई जाती है—87 साल पुरानी समस्या। उससे पहले, मई में, एक OpenAI मॉडल ने 80 साल पुरानी Erdős इकाई-दूरी प्रतिज्ञप्ति को गलत सिद्ध करने की खबर दी गई। इसी सप्ताह, Columbia के एक PhD छात्र ने GPT-5.6 को एक संरचित Codex वर्कफ़्लो के साथ प्रयोग कर पाँच दिनों में छह खुली Erdős समस्याएँ हल कीं। एक शोधकर्ता के शब्दों में, इन प्रणालियों की ताकत खारिज करने में है, साबित करने में नहीं। एक प्रतिवाद उदाहरण एक अकेला गवाह है जिसे आप जाँच सकते हैं; एक प्रमाण को हर स्थिति ढकनी पड़ती है। यही विषमता पहले कौन-सी समस्याएँ गिरेंगी, यह तय करती लगती है।

व्यावहारिक निष्कर्ष यह नहीं है कि "AI गणित हल कर देता है।" जो हम देख रहे हैं वह है AI एक धैर्यवान, संयोज्य रूप से सर्वसम्पूर्ण खोज-सहयोगी के रूप में काम कर रहा है: जो पैरामीटर परिवारों की गिनती कर सकता है, नाकामी के तरीकों को प्रयास-दर-प्रयास कार्य-स्मृति में थाम सकता है, और सच बता सकता है जब कोई निर्माण बंद नहीं होता। यह एक खास, उपयोगी क्षमता है। और यदि आप समझना चाहें कि यह आगे कहाँ वार कर सकता है, तो सवाल यह नहीं कि कौन-सी प्रतिज्ञप्तियाँ सबसे पुरानी हैं, बल्कि यह कि किन्हें एक अकेले जाँचे जा सकने वाले गवाह से तोड़ा जा सकता है।