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