Generalized distributive law
عام تقسیم کا قانون (جی ڈی ایل) تقسیم کی خاصیت کی عمومی شکل ہے جو ایک عام پیغام منتقل کرنے والے الگورتھم کو جنم دیتا ہے۔ یہ انفارمیشن تھیوری، ڈیجیٹل مواصلات، سگنل پروسیسنگ، شماریات، اور مصنوعی ذہانت کی برادریوں میں بہت سے مصنفین کے کام کی ترکیب ہے۔ قانون اور الگورتھم کو اسی عنوان کے ساتھ سرینیواس ایم اجی اور رابرٹ جے میک ایلیس نے ایک نیم سبق میں متعارف کرایا تھا۔ تعارف "ریاضی میں تقسیم کا قانون ضرب اور اضافے کی کارروائیوں سے متعلق قانون ہے، جسے علامتی طور پر بیان کیا گیا ہے، یعنی یک جہتی عنصر کو تقسیم کیا جاتا ہے، یا علیحدہ طور پر لاگو کیا جاتا ہے، بائنومیل عنصر کی ہر اصطلاح پر، جس کے نتیجے میں پروڈکٹ ہوتا ہے"-برٹانیکا جیسا کہ تعریف سے مشاہدہ کیا جا سکتا ہے، تقسیم کے قانون کو ریاضی کے اظہار میں لاگو کرنے سے اس میں کارروائیوں کی تعداد کم ہو جاتی ہے۔ پچھلی مثال میں کارروائیوں کی کل تعداد تین (دو ضرب اور ایک اضافہ) سے گھٹ کر دو (ایک ضرب اور ایک اضافہ) ہو گئی۔ تقسیم کے قانون کی عمومی کاری تیز الگورتھم کے ایک بڑے خاندان کی طرف لے جاتی ہے۔ اس میں ایف ایف ٹی اور وٹربی الگورتھم شامل ہیں۔ اس کی وضاحت نیچے دی گئی مثال میں زیادہ رسمی انداز میں کی گئی ہے: کہاں اور حقیقی قدر والے افعال ہیں، اور (کہیں) یہاں ہم نتیجہ حاصل کرنے کے لیے آزاد متغیرات (،، اور) کو "پسماندہ" کر رہے ہیں۔ جب ہم کمپیوٹیشنل پیچیدگی کا حساب لگا رہے ہیں، تو ہم دیکھ سکتے ہیں کہ ہر جوڑے کے لیے، ٹرپلٹ کی وجہ سے اصطلاحات ہیں جن کی تشخیص میں حصہ لینے کی ضرورت ہے جس میں ہر مرحلے میں ایک اضافہ اور ایک ضرب ہوتی ہے۔ لہذا، درکار حسابات کی کل تعداد ہے۔ لہذا مندرجہ بالا فنکشن کی غیر علامتی پیچیدگی ہے۔ اگر ہم مساوات کے آر ایچ ایس پر تقسیم کے قانون کو لاگو کرتے ہیں، تو ہمیں درج ذیل ملتے ہیں: اس کا مطلب یہ ہے کہ اسے ایک پروڈکٹ کے طور پر بیان کیا جا سکتا ہے جہاں اور جہاں۔ اب، جب ہم کمپیوٹیشنل پیچیدگی کا حساب لگا رہے ہیں، تو ہم دیکھ سکتے ہیں کہ جب ہم تشخیص کے لیے پروڈکٹ کا استعمال کر رہے ہیں تو اس میں اور ہر ایک میں اضافہ ہوتا ہے اور ضرب ہوتی ہے۔ لہذا، درکار حسابات کی کل تعداد ہے۔ اس لیے حساب کی غیر علامتی پیچیدگی کم ہو کر سے ہو جاتی ہے۔ یہ ایک مثال سے ظاہر ہوتا ہے کہ تقسیم کے قانون کا اطلاق کمپیوٹیشنل پیچیدگی کو کم کرتا ہے جو "تیز الگورتھم" کی اچھی خصوصیات میں سے ایک ہے۔ تاریخ کچھ مسائل جنہوں نے تقسیم کے قانون کو حل کرنے کے لیے استعمال کیا انہیں درج ذیل گروپ کیا جا سکتا ہے۔ ڈیکوڈنگ الگورتھم ایک جی ڈی ایل جیسا الگورتھم گیلیجر کے ذریعے کم کثافت والی برابری چیک کوڈز کو ڈیکوڈنگ کرنے کے لیے استعمال کیا گیا تھا۔ گیلیجر کے کام کی بنیاد پر ٹینر نے ٹینر گراف متعارف کرایا اور گیلیجرز کے کام کو پیغام بھیجنے کی شکل میں ظاہر کیا۔ ٹینرز گراف نے وٹربی الگورتھم کی وضاحت میں بھی مدد کی۔ فورنی کی طرف سے یہ مشاہدہ کیا گیا ہے کہ وٹربی کی ارتقاء کوڈز کی زیادہ سے زیادہ امکانات کی ڈیکوڈنگ میں بھی جی ڈی ایل جیسی عامیت کے الگورتھم کا استعمال کیا گیا ہے۔ 2. فارورڈ بیکورڈ الگورتھم فارورڈ بیکورڈ الگورتھم نے مارکوو چین میں ریاستوں کو ٹریک کرنے کے لیے ایک الگورتھم کے طور پر مدد کی۔ اور یہ بھی جنرلٹی 3 کی طرح جی ڈی ایل کا الگورتھم استعمال کیا گیا تھا۔ مصنوعی ذہانت جنکشن ٹری کے تصور کو اے آئی میں بہت سے مسائل کو حل کرنے کے لیے استعمال کیا گیا ہے۔ بالٹی کے خاتمے کے تصور نے بھی بہت سے تصورات کا استعمال کیا۔ ایم پی ایف کا مسئلہ ایم پی ایف یا کسی پروڈکٹ فنکشن کو حاشیے پر رکھنا ایک عمومی کمپیوٹیشنل مسئلہ ہے جس میں خاص صورت میں بہت سے کلاسیکی مسائل شامل ہیں جیسے مجرد ہڈمارڈ ٹرانسفارم کا حساب لگانا، میموری سے کم چینل پر لکیری کوڈ کی زیادہ سے زیادہ امکانات کی ڈیکوڈنگ، اور میٹرکس چین ضرب۔ جی ڈی ایل کی طاقت اس حقیقت میں مضمر ہے کہ یہ ان حالات پر لاگو ہوتا ہے جن میں اضافے اور ضرب کو عام کیا جاتا ہے۔ اس رویے کی وضاحت کے لیے ایک مواصلاتی سیمیرنگ ایک اچھا فریم ورک ہے۔ اس کی وضاحت آپریٹرز "" اور "" کے ساتھ ایک سیٹ پر کی گئی ہے جہاں اور ایک مواصلاتی مونوائڈز ہیں اور تقسیم کا قانون برقرار رکھتا ہے۔ متغیرات کو اس طرح ہونے دیں کہ ایک محدود سیٹ کہاں ہے اور۔ یہاں۔ اگر اور، جانے دو،،، اور جانے دو۔ فرض کریں کہ کسی فنکشن کی تعریف اس طرح کی گئی ہے، جہاں ایک مواصلاتی سیمیرنگ ہے۔ اس کے علاوہ، مقامی ڈومینز اور مقامی دانے کے طور پر بھی نامزد کیے جاتے ہیں۔ اب گلوبل کرنل کی تعریف اس طرح کی گئی ہے: ایم پی ایف کے مسئلے کی تعریف: ایک یا زیادہ اشاریوں کے لیے، گلوبل کرنل کی-مارجنلائزیشن کی اقدار کی ایک ٹیبل کا حساب لگائیں، جس کی تعریف اس طرح کی گئی ہے۔ یہ مشاہدہ کیا جا سکتا ہے کہ واضح طریقے سے معروضی فعل کی گنتی کے لیے کارروائیوں کی ضرورت ہوتی ہے۔ اس کی وجہ یہ ہے کہ آبجیکٹیو فنکشن کے حساب میں اضافے اور ضرب کی ضرورت ہوتی ہے۔ جی ڈی ایل الگورتھم جس کی وضاحت اگلے حصے میں کی گئی ہے اس کمپیوٹیشنل پیچیدگی کو کم کر سکتا ہے۔ درج ذیل ایم پی ایف کے مسئلے کی ایک مثال ہے۔ چلو اور اس طرح متغیر ہو کہ اور. یہاں اور۔ ان متغیرات کا استعمال کرتے ہوئے دیئے گئے افعال ہیں اور اور ہمیں حساب لگانے اور اس کی وضاحت کرنے کی ضرورت ہے: یہاں مقامی ڈومینز اور مقامی دانے کی تعریف اس طرح کی گئی ہے: معروضی فنکشن کہاں ہے اور معروضی فنکشن کہاں ہے۔ ایک اور مثال پر غور کریں کہ کہاں اور ایک حقیقی قابل قدر فنکشن ہے۔ اب، ہم ایم پی ایف کے مسئلے پر غور کریں گے جہاں مواصلاتی سیمیرنگ کو عام اضافے اور ضرب کے ساتھ حقیقی اعداد کے سیٹ کے طور پر بیان کیا گیا ہے اور مقامی ڈومینز اور مقامی دانے کی تعریف اس طرح کی گئی ہے: اب چونکہ عالمی دانے کو مقامی دانے کے پروڈکٹ کے طور پر بیان کیا گیا ہے، یہ ہے اور مقامی ڈومین میں معروضی فنکشن ہے۔ یہ فنکشن کا ہڈمارڈ ٹرانسفارم ہے۔ لہذا ہم دیکھ سکتے ہیں کہ ہڈمارڈ ٹرانسفارم کا حساب ایم پی ایف کے مسئلے کا ایک خاص معاملہ ہے۔ مزید مثالوں سے یہ ثابت کیا جا سکتا ہے کہ ایم پی ایف کا مسئلہ بہت سے کلاسیکی مسائل کے خصوصی معاملات تشکیل دیتا ہے جیسا کہ اوپر بیان کیا گیا ہے جن کی تفصیلات جی ڈی ایل میں مل سکتی ہیں: ایم پی ایف کے مسئلے کو حل کرنے کے لیے ایک الگورتھم اگر کوئی کسی دیئے گئے سیٹ کے عناصر کے درمیان تعلق تلاش کر سکتا ہے، تو کوئی ایم پی ایف کے مسئلے کو عقیدے کے پھیلاؤ کے تصور کی بنیاد پر حل کر سکتا ہے جو کہ "میسج پاسنگ" تکنیک کا ایک خاص استعمال ہے۔ مطلوبہ تعلق یہ ہے کہ مقامی ڈومینز کے دیئے گئے سیٹ کو جنکشن ٹری میں منظم کیا جا سکتا ہے۔ دوسرے لفظوں میں، ہم ایک گراف تھیوریٹک ٹری بناتے ہیں جس کے عناصر درخت کے چوٹیوں کے طور پر ہوتے ہیں، جیسے کہ کسی بھی دو صوابدیدی چوٹیوں کے لیے کہیں اور کہاں اور ان دونوں چوٹیوں کے درمیان ایک کنارے موجود ہے، پھر متعلقہ لیبلز کا چوراہا، یعنی، ہر سرے پر لیبل کا ایک ذیلی سیٹ ہے جو منفرد راستے پر ہے۔ مثال کے طور پر، مثال 1: درج ذیل نو مقامی ڈومینز پر غور کریں: مقامی ڈومینز کے مذکورہ بالا سیٹ کے لیے، کوئی بھی انہیں جنکشن ٹری میں منظم کر سکتا ہے جیسا کہ ذیل میں دکھایا گیا ہے: اسی طرح اگر مندرجہ ذیل جیسے دوسرے سیٹ کو دیا جائے تو مثال 2: درج ذیل چار مقامی ڈومینز پر غور کریں: پھر صرف ان مقامی ڈومینز کے ساتھ ٹری کی تعمیر ممکن نہیں ہے کیونکہ اقدار کے اس سیٹ میں کوئی مشترکہ ڈومین نہیں ہے جسے اوپر دیے گئے سیٹ کی کسی بھی دو اقدار کے درمیان رکھا جا سکتا ہے۔ تاہم، اگر ذیل میں دکھائے گئے دو ڈمی ڈومینز کو شامل کیا جائے تو اپ ڈیٹ شدہ سیٹ کو جنکشن ٹری میں منظم کرنا ممکن اور آسان بھی ہوگا۔ 5.، 6.، اسی طرح ڈومینز کے ان سیٹ کے لیے، جنکشن ٹری اس طرح نظر آتا ہے جیسے نیچے دکھایا گیا ہے: جنرلائزڈ ڈسٹری بیوٹو لا (جی ڈی ایل) الگورتھم ان پٹ: مقامی ڈومینز کا ایک سیٹ۔ آؤٹ پٹ: ڈومینز کے دیئے گئے سیٹ کے لیے، مسئلے کو حل کرنے کے لیے درکار کارروائیوں کی ممکنہ کم از کم تعداد کا حساب لگایا جاتا ہے۔ لہذا، اگر اور جنکشن ٹری میں کسی کنارے سے جڑے ہوئے ہیں، تو سے ایک پیغام کسی فنکشن کے ذریعہ دی گئی اقدار کا ایک سیٹ/ٹیبل ہے::۔ تمام افعال سے شروع کرنا یعنی۔ دیئے گئے ٹری میں اور اس کے تمام امتزاج کے لیے، یکساں طور پر بیان کیا گیا ہے اور جب کسی خاص پیغام کو اپ ڈیٹ کیا جاتا ہے، تو یہ نیچے دی گئی مساوات کی پیروی کرتا ہے۔ = جہاں کا مطلب ہے کہ یہ درخت سے ملحقہ ورٹیکس ہے۔ اسی طرح ہر ورٹیکس کی ایک حالت ہوتی ہے جس کی تعریف ایک ٹیبل کے طور پر کی جاتی ہے جس میں فنکشن کی اقدار ہوتی ہیں، جس طرح پیغامات یکساں طور پر 1 پر شروع ہوتے ہیں، اس کی حالت کو مقامی کرنل کے طور پر بیان کیا جاتا ہے، لیکن جب بھی اپ ڈیٹ ہوتا ہے، تو یہ مندرجہ ذیل مساوات کی پیروی کرتا ہے: الگورتھم کا بنیادی کام ان پٹ کے طور پر مقامی ڈومینز کے دیئے گئے سیٹ کے لیے، ہم یہ معلوم کرتے ہیں کہ کیا ہم ایک جنکشن ٹری بنا سکتے ہیں، یا تو براہ راست سیٹ کا استعمال کرکے یا پہلے سیٹ میں ڈمی ڈومینز کو شامل کرکے اور پھر جنکشن ٹری بنا کر، اگر تعمیراتی جنکشن ممکن نہیں ہے تو الگورتھم آؤٹ پٹ کہ دیئے گئے مساوات کے مسئلے کو شمار کرنے کے لیے مراحل کی تعداد کو کم کرنے کا کوئی طریقہ نہیں ہے، لیکن ایک بار جب ہمارے پاس جنکشن ٹری ہو جائے تو الگورتھم کو پیغامات کو شیڈول کرنا پڑے گا اور اسٹیٹس کا حساب لگانا پڑے گا، ایسا کرنے سے ہم جان سکتے ہیں کہ اقدامات کہاں ہیں۔ میسج پاسنگ اور اسٹیٹ کمپیوٹیشن کا شیڈولنگ دو خاص معاملات ہیں جن کے بارے میں ہم یہاں بات کرنے جا رہے ہیں یعنی سنگل ورٹیکس پروبلم جس میں آبجیکٹیو فنکشن صرف ایک ورٹیکس پر شمار کیا جاتا ہے اور دوسرا آل ورٹیسیس پروبلم ہے جہاں مقصد تمام عمودی حصوں پر آبجیکٹیو فنکشن کا حساب لگانا ہے۔ آئیے سنگل ورٹیکس کے مسئلے سے شروع کرتے ہیں، جی ڈی ایل ہر کنارے کو ٹارگٹڈ ورٹیکس کی طرف موڑ کر شروع کرے گا۔ یہاں پیغامات صرف ہدف شدہ سرے کی سمت میں بھیجے جاتے ہیں۔ نوٹ کریں کہ تمام ہدایت شدہ پیغامات صرف ایک بار بھیجے جاتے ہیں۔ پیغامات پتی کے نوڈس سے شروع ہوتے ہیں (جہاں ڈگری 1 ہے) ہدف کے سرے کی طرف اوپر جاتے ہیں۔ پیغام پتوں سے اس کے والدین تک جاتا ہے اور پھر وہاں سے ان کے والدین تک جاتا ہے اور اسی طرح جب تک کہ یہ ہدف کے سرے تک نہ پہنچ جائے۔ ہدف ورٹیکس اپنی حالت کا حساب تب ہی کرے گا جب اسے اپنے تمام پڑوسیوں سے تمام پیغامات موصول ہوں گے۔ ایک بار جب ہمارے پاس حالت ہوتی ہے، تو ہمیں جواب مل جاتا ہے اور اس لیے الگورتھم ختم ہو جاتا ہے۔ مثال کے طور پر، آئیے اوپر دیئے گئے مقامی ڈومینز کے سیٹ سے بنائے گئے جنکشن ٹری پر غور کریں۔ مثال 1 سے سیٹ، اب ان ڈومینز کے لیے شیڈولنگ ٹیبل ہے (جہاں ٹارگٹ ورٹیکس ہے)۔ اس طرح سنگل ورٹیکس جی ڈی ایل کی پیچیدگی کو ریاضی کی کارروائیوں کے طور پر دکھایا جا سکتا ہے جہاں (نوٹ: مندرجہ بالا مساوات کی وضاحت مضمون میں بعد میں بیان کی گئی ہے) کا لیبل ہے۔ کی ڈگری ہے (یعنی۔ v) سے ملحقہ عمودی حصوں کی تعداد۔ آل ورٹیسز کے مسئلے کو حل کرنے کے لیے، ہم جی ڈی ایل کو کئی طریقوں سے شیڈول کر سکتے ہیں، ان میں سے کچھ متوازی نفاذ ہیں جہاں ہر دور میں، ہر ریاست کو اپ ڈیٹ کیا جاتا ہے اور ہر پیغام کا حساب لگایا جاتا ہے اور ایک ہی وقت میں منتقل کیا جاتا ہے۔ اس قسم کے نفاذ میں ریاستیں اور پیغامات راؤنڈز کی تعداد کے بعد مستحکم ہوں گے جو زیادہ سے زیادہ درخت کے قطر کے برابر ہے۔ اس مقام پر چوٹیوں کی تمام ریاستیں مطلوبہ معروضی فعل کے برابر ہوں گی۔ اس مسئلے کے لیے جی ڈی ایل کو شیڈول کرنے کا ایک اور طریقہ سیریل نفاذ ہے جہاں یہ سنگل ورٹیکس مسئلے سے ملتا جلتا ہے سوائے اس کے کہ ہم الگورتھم کو اس وقت تک نہیں روکتے جب تک کہ مطلوبہ سیٹ کے تمام عمودی حصوں کو ان کے تمام پڑوسیوں سے تمام پیغامات نہ مل جائیں اور ان کی حالت کا حساب نہ لگائیں۔ اس طرح اس عمل درآمد کے لیے درکار ریاضی کی تعداد زیادہ تر ریاضی کی کارروائیوں پر ہوتی ہے۔ جنکشن ٹری کی تعمیر جنکشن ٹری کی تعمیر کی کلید مقامی ڈومین گراف میں ہوتی ہے، جو کہ عمودی نقاط کے ساتھ ایک مکمل گراف ہے۔ ہر مقامی ڈومین کے لیے ایک، جس میں کنارے کا وزن بیان کیا گیا ہے۔ اگر، تو ہم کہتے ہیں کہ اس میں موجود ہے۔ (زیادہ سے زیادہ وزن والے پھیلے ہوئے درخت کا وزن) سے ظاہر ہوتا ہے، جس کی تعریف اس سیٹ میں موجود عناصر کی تعداد n سے ہوتی ہے۔ مزید وضاحت اور تفصیلات کے لیے، براہ کرم ان کا حوالہ دیں۔ شیڈولنگ تھیوریم ایک جنکشن ٹری ہے جس میں ورٹیکس سیٹ اور ایج سیٹ ہے۔ اس الگورتھم میں، پیغامات کسی بھی کنارے پر دونوں سمتوں میں بھیجے جاتے ہیں، لہذا ہم کنارے کے سیٹ E کو عمودی جوڑوں کے ترتیب شدہ جوڑوں کے سیٹ کے طور پر کہہ سکتے ہیں۔ مثال کے طور پر، شکل 1 سے اس کی تعریف مندرجہ ذیل طور پر کی جا سکتی ہے نوٹ: اوپر آپ کو وہ تمام ممکنہ ہدایات دیتا ہے جو ایک پیغام درخت میں سفر کر سکتا ہے۔ جی ڈی ایل کے شیڈول کو ذیلی سیٹوں کی ایک محدود ترتیب کے طور پر بیان کیا گیا ہے۔ جس کی نمائندگی عام طور پر {} کے ذریعہ کی جاتی ہے، الگورتھم کو چلانے کے دور کے دوران پیغامات کا سیٹ کہاں اپ ڈیٹ کیا جاتا ہے۔ کچھ اشارے کی وضاحت/دیکھنے کے بعد، ہم دیکھیں گے کہ تھیوریم کا کہنا ہے کہ، جب ہمیں ایک شیڈول دیا جاتا ہے، تو متعلقہ پیغام ٹریلیس ورٹیکس سیٹ کے ساتھ ایک محدود ہدایت شدہ گراف کے طور پر ہوتا ہے، جس میں ایک عام عنصر کی نشاندہی کی جاتی ہے، پھر پیغام کے گزرنے کی تکمیل کے بعد، ورٹیکس پر ریاست کا مقصد بیان کیا جائے گا اور آئی ایف ایف میں کمپیوٹیشنل پیچیدگی کا راستہ ہوگا۔ یہاں ہم حساب کے لیے درکار ریاضیاتی کارروائیوں کی تعداد کے لحاظ سے ایم پی ایف کے مسئلے کو حل کرنے کی پیچیدگی کی وضاحت کرنے کی کوشش کرتے ہیں۔ یعنی۔ ہم عام طریقہ کار کا استعمال کرتے ہوئے حساب لگانے کے لیے درکار کارروائیوں کی تعداد کا موازنہ کرتے ہیں (یہاں عام طریقہ سے ہمارا مطلب ان طریقوں سے ہے جو مختصر طریقوں میں میسج پاسنگ یا جنکشن ٹری کا استعمال نہیں کرتے ہیں جو جی ڈی ایل کے تصورات کو استعمال نہیں کرتے ہیں) اور عمومی تقسیم قانون کا استعمال کرتے ہوئے کارروائیوں کی تعداد۔ مثال: سب سے آسان صورت پر غور کریں جہاں ہمیں مندرجہ ذیل اظہار کا حساب لگانے کی ضرورت ہے۔ بے وقوفانہ طور پر اس اظہار کا اندازہ کرنے کے لیے دو ضرب اور ایک اضافہ درکار ہوتا ہے۔ تقسیم کے قانون کا استعمال کرتے ہوئے اظہار کیے جانے پر اظہار کو ایک سادہ اصلاح کے طور پر لکھا جا سکتا ہے جو کارروائیوں کی تعداد کو ایک اضافے اور ایک ضرب تک کم کر دیتا ہے۔ مذکورہ بالا بیان کردہ مثال کی طرح ہم جی ڈی ایل کا اطلاق کرکے زیادہ سے زیادہ کم آپریشن انجام دینے کے لیے مساوات کو مختلف شکلوں میں ظاہر کریں گے۔ جیسا کہ پچھلے حصوں میں بیان کیا گیا ہے کہ ہم جنکشن ٹری کے تصور کو استعمال کرتے ہوئے مسئلہ کو حل کرتے ہیں۔ ان درختوں کے استعمال سے حاصل ہونے والی اصلاح کا موازنہ درختوں پر نیم گروپ کے مسئلے کو حل کرنے سے حاصل ہونے والی اصلاح سے کیا جا سکتا ہے۔ مثال کے طور پر، اعداد کے گروپ کی کم از کم تعداد تلاش کرنے کے لیے ہم مشاہدہ کر سکتے ہیں کہ اگر ہمارے پاس ایک درخت ہے اور تمام عناصر درخت کے نیچے ہیں، تو ہم متوازی طور پر کم از کم دو آئٹمز کا موازنہ کر سکتے ہیں اور نتیجہ خیز کم از کم والدین کو لکھا جائے گا۔ جب اس عمل کو درخت کے اوپر پھیلایا جائے گا تو عناصر کے گروپ کا کم از کم جڑ پر پایا جائے گا۔ پیغام گزرنے کا استعمال کرتے ہوئے جنکشن ٹری کو حل کرنے کی پیچیدگی درج ذیل ہے۔ ہم پہلے استعمال ہونے والے فارمولے کو درج ذیل شکل میں دوبارہ لکھتے ہیں۔ یہ ورٹیکس v سے w---- پیغام کی مساوات پر بھیجے جانے والے پیغام کے لیے ایکون ہے۔ اسی طرح ہم ورٹیکس v کی حالت کا حساب لگانے کے لیے مساوات کو اس طرح دوبارہ لکھتے ہیں: ہم پہلے سنگل ورٹیکس کے مسئلے کا تجزیہ کریں گے اور فرض کریں گے کہ ٹارگٹ ورٹیکس ہے اور اس لیے ہمارے پاس سے ایک کنارے ہے۔ فرض کریں کہ ہمارے پاس ایک کنارے ہے ہم پیغام کی مساوات کا استعمال کرتے ہوئے پیغام کا حساب لگاتے ہیں۔ حساب لگانے کے لیے اضافے اور ضرب کی ضرورت ہوتی ہے۔ (ہم اس کی نمائندگی کرتے ہیں۔) لیکن اس لیے بہت سے امکانات ہوں گے۔ اس طرح پورے پیغام میں اضافے اور ضرب کی ضرورت ہوگی۔ درخت کے کناروں کی طرف پیغام بھیجنے کے لیے درکار ریاضی کی کارروائیوں کی کل تعداد اضافہ اور ضرب ہوگی۔ ایک بار جب تمام پیغامات منتقل ہو جاتے ہیں تو الگورتھم اسٹیٹ کے حساب کے ساتھ ختم ہو جاتا ہے۔ اسٹیٹ کے حساب کے لیے مزید ضرب کی ضرورت ہوتی ہے۔ اس طرح حالت کا حساب لگانے کے لیے درکار حسابات کی تعداد ذیل میں اضافے اور ضرب کے طور پر دی گئی ہے۔ اس طرح حسابات کی تعداد کا مجموعی مجموعہ ہے---- جہاں ایک کنارہ ہے اور اس کے سائز کی وضاحت کی گئی ہے۔ اگر ہم کنارے کی پیچیدگی کو اس طرح بیان کرتے ہیں تو، اس طرح لکھا جا سکتا ہے کہ اب ہم شکل 1 میں بیان کردہ مسئلے کے لیے کنارے کی پیچیدگی کا حساب اس طرح کرتے ہیں کہ کل پیچیدگی ایسی ہوگی جو براہ راست طریقہ کار کے مقابلے میں کافی کم ہے۔ (یہاں براہ راست طریقہ سے ہمارا مطلب ان طریقوں سے ہے جو پیغام منتقل کرنے کا استعمال نہیں کرتے ہیں۔ براہ راست طریقہ استعمال کرنے میں لگنے والا وقت ہر نوڈ پر پیغام کا حساب لگانے کے برابر ہوگا اور ہر نوڈ کی حالت کا حساب لگانے کے لیے وقت ہوگا۔) اب ہم آل ورٹیکس کے مسئلے پر غور کرتے ہیں جہاں پیغام کو دونوں سمتوں میں بھیجنا پڑے گا اور دونوں سروں پر حالت کا حساب لگانا ہوگا۔ اس میں وقت لگے گا لیکن پری کمپیوٹنگ سے ہم ضرب کی تعداد کو کم کر سکتے ہیں۔ یہاں ورٹیکس کی ڈگری ہے۔ مثال: اگر اعداد کے ساتھ کوئی سیٹ ہے۔ واضح کے بجائے زیادہ سے زیادہ ضرب کے ساتھ کے تمام ڈی پروڈکٹس کا حساب لگانا ممکن ہے۔ ہم یہ مقداروں کو پہلے سے گن کر کرتے ہیں اور اس میں ضرب لگتی ہے۔ جب جنکشن ٹری کی تعمیر کی بات آتی ہے تو ہم زیادہ سے زیادہ کچھ نہیں کر سکتے ہیں سوائے اس کے کہ ہمارے پاس زیادہ سے زیادہ وزن والے درخت ہو سکتے ہیں اور ہمیں کم سے کم کے ساتھ پھیلے ہوئے درخت کا انتخاب کرنا چاہیے اور بعض اوقات اس کا مطلب یہ ہو سکتا ہے کہ جنکشن ٹری کی پیچیدگی کو کم کرنے کے لیے مقامی ڈومین کا اضافہ کیا جائے۔ ایسا لگ سکتا ہے کہ جی ڈی ایل صرف اس صورت میں درست ہے جب مقامی ڈومینز کو جنکشن ٹری کے طور پر ظاہر کیا جا سکے۔ لیکن ان صورتوں میں بھی جہاں سائیکل ہوتے ہیں اور متعدد تکرار ہوتے ہیں پیغامات تقریبا معروضی فعل کے برابر ہوں گے۔ کم کثافت والی برابری چیک کوڈز کے لیے گیلیجر-ٹینر-وائبرگ الگورتھم پر تجربات اس دعوے کے حامی تھے۔ حوالہ جات انفارمیشن تھیوری الگورتھم گرافیکل ماڈل ڈیجیٹل سگنل پروسیسنگ