22 سال کے شک کے بعد: پیغامات ملانا انہیں راستوں پر بھیجنے سے بہتر نکلا
کیبلوں کے ایک ایسے نیٹ ورک کا تصور کریں جس میں کئی بھیجنے والے ہر ایک اپنے اپنے وصول کنندہ تک پہنچنا چاہتے ہیں۔ روایتی طریقہ روٹنگ ہے: ہر پیغام ایک پارسل کی طرح ایک یا زیادہ راستوں پر سفر کرتا ہے، اور ٹریفک کو کسی بھی تناسب میں بہت سے راستوں میں بانٹا بھی جا سکتا ہے۔ نیٹ ورک کوڈنگ (network coding) ایک اور آزادی کا اضافہ کرتی ہے: درمیانی نوڈز موصول ہونے والے پیغامات کو محض آگے بھیجنے کے بجائے انہیں یکجا کر سکتے ہیں — مثلاً انہیں جمع کر کے۔
سوال یہ ہے کہ کیا یہ آزادی کبھی زیادہ ڈیٹا گزرنے دیتی ہے۔ مقالہ غیر سمتی نیٹ ورکس پر توجہ دیتا ہے، جہاں ایک کیبل کسی بھی سمت میں ڈیٹا لے جا سکتی ہے لیکن دونوں سمتیں ایک ہی گنجائش میں شریک ہوتی ہیں۔
ایک قیاس جس کی صورت بہ صورت تصدیق ہوئی
2004 میں لی اور لی (Li and Li) نے قیاس کیا کہ اس صورتحال میں کوڈنگ جزوی (فریکشنل) روٹنگ کے مقابلے میں کوئی برتری نہیں دیتی؛ ہاروی، کلائن برگ اور راسالا لیہمن (Harvey, Kleinberg and Rasala Lehman) نے آزادانہ طور پر یہی قیاس پیش کیا۔ اگلی دو دہائیوں میں نیٹ ورکس کی ایک کے بعد ایک قسم کے لیے اس کی تصدیق ہوئی — دو سیشن، بعض مسطح نیٹ ورکس، زیادہ سے زیادہ چھ کوڈنگ نوڈز والے نیٹ ورکس، اور دیگر — مگر عمومی طور پر یہ کبھی طے نہیں ہوا۔ پیچیدگی کے نظریے کے دیگر نتائج، جیسے بیرونی میموری میں صحیح اعداد کی ترتیب اور ضرب کے سرکٹس کے لیے زیریں حدود، یہاں تک کہ اسے درست فرض کر کے ثابت کیے جا چکے تھے۔
معلوم نظریہ پہلے ہی داؤ کو محدود کر چکا تھا: کوڈنگ روٹنگ پر زیادہ سے زیادہ لوگارتھمی عامل سے برتری لے سکتی ہے۔ اور بریورمین، گرگ اور شوارٹزمین (Braverman, Garg and Schvartzman) کے 2017 کے ایک نتیجے نے دکھایا کہ کوڈنگ کی واضح برتری والے صرف ایک نیٹ ورک کو بڑھا کر کہیں بڑا فرق بنایا جا سکتا ہے۔ سب کچھ ایک محدود مثال ڈھونڈنے پر آ ٹھہرا تھا۔
جمع کرنا کافی ہے
ضمیمہ بنیادی ترکیب پیش کرتا ہے، جو دکھاتی ہے کہ ملانا کیوں مدد کر سکتا ہے۔ کئی ذرائع کو ایک مرکزی نوڈ v کے گرد رکھیں، ان کے وصول کنندگان کو ایک اور مرکزی نوڈ w کے گرد، اور v اور w کو ایک کیبل سے جوڑ دیں۔ ہر ذریعے کے دوسرے وصول کنندگان تک چھوٹے ذیلی راستے بھی ہیں۔ تین مرحلوں میں درمیانی کیبل تمام پیغامات کا مجموعہ لے جاتی ہے؛ ہر وصول کنندہ یہ مجموعہ اور ذیلی راستوں سے باقی پیغامات حاصل کرتا ہے، اور تفریق کے ذریعے اپنا پیغام نکال لیتا ہے۔ درمیانی کیبل کے بغیر ہر ذریعہ اپنے وصول کنندہ سے پانچ چھلانگوں کے فاصلے پر ہے۔
ہیپلر، وائس اور زوزک (Haeupler, Wajc and Zuzic) کے سابقہ کام سے لی گئی یہ ترکیب کوڈنگ کو تیز تر بناتی ہے، لیکن اکیلے زیادہ لے جانے کے قابل نہیں بناتی: ایک لمبا راستہ اب بھی تیز رفتار مسلسل بہاؤ (پائپ لائن) چلا سکتا ہے۔
ایک سرکٹ جو نیٹ ورک بن گیا
ٹورنٹو یونیورسٹی کے شِنڈان ژانگ (Xindan Zhang) اور باؤچُن لی (Baochun Li)، اور سنگھوا یونیورسٹی کے زونگ پینگ لی (Zongpeng Li) نے گمشدہ قدم ڈھونڈ نکالا۔ وہ ایک مختصر کوڈ کو ایک قابلِ واپسی حساب میں بدلتے ہیں — قابلِ معکوس صحیح عددی جمع کا ایک سرکٹ جو حساب کرتا ہے، نتیجہ نقل کرتا ہے، پھر اپنا درمیانی کام الٹ دیتا ہے۔ پھر وہ ایک نیا نیٹ ورک بناتے ہیں جس کی طبعی کیبلیں اسی سرکٹ کے تار ہیں، اور حساب کے ہر رجسٹر کو، بشمول عارضی رجسٹروں کے، اس کی اپنی بھیجنے والے–وصول کنندہ کی طلب دیتے ہیں۔
تاروں کے ساتھ “وقت” کا محتاط حساب باقی کام کر دیتا ہے۔ تمام تاروں پر جمع کرنے سے لمبائیاں بالکل ان کم سے کم فاصلوں کے برابر نکلتی ہیں جو طلبوں کو طے کرنے ہیں۔ مگر مقررہ طلبیں کچھ ایسے گیٹس سے نہیں بچ سکتیں جن کی قیمت دو اضافی اکائیاں ہے۔ چنانچہ روٹنگ کو لازماً مکمل شرح سے کم رہنا پڑتا ہے، جبکہ کوڈ ہر کیبل کو ٹھیک ایک بار استعمال کرتا ہے اور، بہت سے بلاکس پر پائپ لائن کی صورت میں چلایا جائے تو، ایک کی شرح کے قریب پہنچ جاتا ہے۔
کیا ثابت ہوا
- ایک محدود مربوط نیٹ ورک، جس میں ہر نوڈ زیادہ سے زیادہ تین دوسرے نوڈز سے جڑا ہے اور ہر کیبل کی گنجائش ایک اکائی ہے، جس پر ایک سادہ ثنائی (بائنری) خطی کوڈ بہترین ممکنہ جزوی روٹنگ کو مات دیتا ہے۔ 2004 کا قیاس غلط ہے۔
- یہی صحیح عددی تعمیر بیک وقت ہر محدود فیلڈ اور ہر غیر بدیہی (non-trivial) محدود ایبیلین گروپ پر کام کرتی ہے۔
- نقول کو بار بار یکجا کر کے مصنفین نیٹ ورکس کے لامحدود خاندان بناتے ہیں جن میں کوڈنگ مکمل شرح کے قریب پہنچتی ہے جبکہ روٹنگ 1/log n کی ایک طاقت کی طرح گرتی ہے — یعنی ایک پولی لوگارتھمی برتری۔
مقالہ اپنی تردیدی مثال میں نوڈز کی تعداد نہیں بتاتا۔ اس کا صرف بنیادی بلاک ہی ایک ایسا کوڈ ہے جو 13,122 مرحلوں تک چلتا ہے۔
مشین سے جانچا گیا
محدود تردیدی مثال اور خاندانی مسئلہ دونوں کو ثبوت معاون Lean میں باضابطہ شکل دی گئی ہے۔ مصنفین کے مطابق 2,472 اعلانات اور 1,755 مسئلوں کا جائزہ دکھاتا ہے کہ ثبوت صرف Lean کے تین معیاری اصولِ موضوعہ استعمال کرتے ہیں، اور کوئی نامکمل ثبوت نہیں؛ ایک نئے ماحول میں آزادانہ دوبارہ جانچ بھی کامیاب رہی، اگرچہ اسی Lean کرنل کے ساتھ۔
کیا ابھی کھلا ہے
مصنفین تین سوالات گنواتے ہیں: ان کی محدود مثال پر برتری کا حقیقی حجم، کیا معلوم لوگارتھمی بالائی حد واقعی حاصل ہوتی ہے، اور کیا کوئی چھوٹی تردیدی مثال موجود ہے۔ ان کا آخری جملہ صورتحال کا خلاصہ کرتا ہے: “پتا چلا کہ کوڈنگ غیر سمتی نیٹ ورکس میں واقعی مدد کرتی ہے؛ یہ کتنی مدد کر سکتی ہے، یہ ابھی دیکھنا باقی ہے۔”
مصنوعی ذہانت کے استعمال کا اعلان۔ ایک حاشیے میں بتایا گیا ہے کہ OpenAI کے GPT-6 Astra نے ثبوتوں اور Lean کوڈ کی تیاری میں مدد کی۔