22 साल के संदेह के बाद: संदेशों को मिलाना उन्हें रास्तों से भेजने से बेहतर निकला

केबलों के एक नेटवर्क की कल्पना कीजिए जिसमें कई प्रेषक हैं और हर एक अपने-अपने प्राप्तकर्ता तक पहुँचना चाहता है। क्लासिक तरीक़ा है रूटिंग (routing): हर संदेश पार्सल की तरह एक या अधिक रास्तों पर चलता है, और ट्रैफ़िक को किसी भी अनुपात में कई रास्तों में बाँटा भी जा सकता है। नेटवर्क कोडिंग (network coding) एक और आज़ादी जोड़ती है: बीच के नोड अपने पास आए संदेशों को केवल आगे बढ़ाने के बजाय उन्हें मिला सकते हैं — उदाहरण के लिए उन्हें जोड़कर।

सवाल यह है कि क्या यह आज़ादी कभी ज़्यादा डेटा को गुज़रने देती है। शोधपत्र अदिष्ट (undirected) नेटवर्कों पर केंद्रित है, जहाँ एक केबल किसी भी दिशा में डेटा ले जा सकती है, लेकिन दोनों दिशाएँ एक ही क्षमता साझा करती हैं।

एक अनुमान जो मामले-दर-मामले सही निकला

2004 में ली और ली (Li and Li) ने अनुमान लगाया कि इस स्थिति में भिन्नात्मक रूटिंग की तुलना में कोडिंग से कोई लाभ नहीं होता; हार्वी, क्लाइनबर्ग और रसाला लेहमन (Harvey, Kleinberg and Rasala Lehman) ने स्वतंत्र रूप से यही अनुमान प्रस्तुत किया। अगले दो दशकों में यह नेटवर्कों के एक के बाद एक वर्ग के लिए सही पाया गया — दो सत्र, कुछ समतलीय नेटवर्क, अधिकतम छह कोडिंग नोड वाले नेटवर्क, और भी — पर सामान्य रूप में कभी तय नहीं हुआ। जटिलता-सिद्धांत के कुछ अन्य परिणाम, जैसे बाहरी मेमोरी में पूर्णांकों को क्रमबद्ध करने और गुणन-परिपथों के लिए निम्न सीमाएँ, तो इसे मानकर ही सिद्ध किए गए थे।

ज्ञात सिद्धांत पहले ही दाँव को सीमित कर चुका था: कोडिंग रूटिंग को अधिकतम एक लघुगणकीय गुणक से ही पछाड़ सकती है। और ब्रेवरमैन, गर्ग और श्वार्ट्ज़मैन (Braverman, Garg and Schvartzman) के 2017 के एक परिणाम ने दिखाया था कि सख़्त कोडिंग-बढ़त वाले एक अकेले नेटवर्क को एक कहीं बड़े अंतर में बदला जा सकता है। सब कुछ एक सीमित उदाहरण खोजने पर टिका था।

जोड़ना ही काफ़ी है

परिशिष्ट मूल युक्ति देता है, जो दिखाती है कि मिलाना क्यों मदद कर सकता है। कई स्रोतों को एक हब v के चारों ओर रखिए, उनके प्राप्तकर्ताओं को दूसरे हब w के चारों ओर, और v व w को एक केबल से जोड़िए। हर स्रोत के पास दूसरे प्राप्तकर्ताओं तक जाने वाले छोटे बग़ली रास्ते भी हैं। तीन चरणों में बीच वाली केबल सभी संदेशों का योग ले जाती है; हर प्राप्तकर्ता को वह योग और बग़ली रास्तों से बाक़ी संदेश मिलते हैं, और वह घटाकर अपना संदेश निकाल लेता है। बीच वाली केबल के बिना हर स्रोत अपने प्राप्तकर्ता से पाँच क़दम (hops) दूर है।

हॉप्लर, वाज्क और ज़ुज़िक (Haeupler, Wajc and Zuzic) के पहले के काम से आई यह युक्ति कोडिंग को तेज़ बनाती है, पर अकेले दम पर ज़्यादा ले जाने लायक़ नहीं: एक लंबा रास्ता भी ऊँची दर वाली पाइपलाइन चला सकता है।

नेटवर्क में बदला गया एक परिपथ

टोरंटो विश्वविद्यालय के शिनदान झांग (Xindan Zhang) और बाओचुन ली (Baochun Li), और सिंगहुआ विश्वविद्यालय के ज़ोंगपेंग ली (Zongpeng Li) ने वह छूटा हुआ क़दम खोज निकाला। वे एक छोटे कोड को एक उत्क्रमणीय गणना (reversible computation) में बदलते हैं — व्युत्क्रमणीय पूर्णांक जोड़ों का एक परिपथ, जो गणना करता है, परिणाम की प्रतिलिपि बनाता है, फिर अपने बीच के काम को उलट देता है। फिर वे एक नया नेटवर्क बनाते हैं जिसकी भौतिक केबलें उसी परिपथ के तार हैं, और गणना के हर रजिस्टर को, अस्थायी (scratch) रजिस्टरों समेत, उसकी अपनी प्रेषक-प्राप्तकर्ता माँग देते हैं।

तारों के साथ “समय” का एक सावधान हिसाब बाक़ी काम कर देता है। सभी तारों पर जोड़ने पर, लंबाइयाँ ठीक उन न्यूनतम दूरियों के बराबर होती हैं जो माँगों को तय करनी हैं। लेकिन निर्धारित माँगें कुछ ऐसे गेटों से बच नहीं सकतीं जिनकी क़ीमत दो अतिरिक्त इकाइयाँ है। इसलिए रूटिंग पूरी दर से सख़्ती से पीछे रह जाती है, जबकि कोड हर केबल का ठीक एक बार इस्तेमाल करता है और कई ब्लॉकों पर पाइपलाइन करने पर एक की दर के क़रीब पहुँचता है।

क्या सिद्ध हुआ है

एक सीमित जुड़ा हुआ नेटवर्क, जिसमें हर नोड अधिकतम तीन दूसरों से जुड़ा है और हर केबल की क्षमता एक इकाई है, जिस पर एक सरल द्विआधारी रैखिक कोड सबसे अच्छी संभव भिन्नात्मक रूटिंग को पछाड़ देता है। 2004 का अनुमान ग़लत है।
वही पूर्णांक-निर्माण एक साथ हर सीमित क्षेत्र (finite field) और हर अतुच्छ सीमित आबेली समूह पर काम करता है।
प्रतियों को बार-बार जोड़कर लेखक नेटवर्कों के अनंत परिवार बनाते हैं, जिनमें कोडिंग पूरी दर के क़रीब पहुँचती है जबकि रूटिंग 1/log n की किसी घात की तरह गिरती है — एक बहुलघुगणकीय (polylogarithmic) बढ़त।

शोधपत्र अपने प्रति-उदाहरण में नोडों की संख्या नहीं बताता। उसका मूल खंड ही एक ऐसा कोड है जो 13,122 चरणों तक चलता है।

मशीन से जाँचा गया

सीमित प्रति-उदाहरण और परिवार-प्रमेय, दोनों को Lean प्रूफ़ असिस्टेंट में औपचारिक रूप दिया गया है। लेखकों के अनुसार, 2,472 घोषणाओं और 1,755 प्रमेयों की एक जाँच से पता चलता है कि प्रमाण केवल Lean के तीन मानक स्वयंसिद्धों का इस्तेमाल करते हैं, कोई अधूरा प्रमाण नहीं है; एक नए परिवेश में की गई स्वतंत्र पुनर्जाँच भी सफल रही, हालाँकि उसी Lean कर्नेल के साथ।

क्या अभी खुला है

लेखक तीन सवाल गिनाते हैं: उनके सीमित उदाहरण पर बढ़त का असली आकार, क्या ज्ञात लघुगणकीय छत सचमुच छुई जाती है, और क्या कोई छोटा प्रति-उदाहरण मौजूद है। उनका आख़िरी वाक्य स्थिति का सार बताता है: “पता चलता है कि अदिष्ट नेटवर्कों में कोडिंग सचमुच मदद करती है; वह कितनी मदद कर सकती है, यह देखना बाक़ी है।”

AI के इस्तेमाल की घोषणा। एक फ़ुटनोट में कहा गया है कि OpenAI के GPT-6 Astra ने प्रमाणों और Lean कोड को विकसित करने में सहायता की।