ایک آسان آواز والا مسئلہ ہماری کائنات کے لیے بہت زیادہ نمبر پیدا کرتا ہے۔ کوانٹا میگزین

ایسا اکثر نہیں ہوتا ہے کہ 5 سال کے بچے کمپیوٹر سائنس کی سرحدوں پر سوالات کو سمجھ سکتے ہیں، لیکن ایسا ہو سکتا ہے۔ فرض کریں، مثال کے طور پر، کہ ایلس نامی کنڈرگارٹنر کے پاس دو سیب ہیں، لیکن وہ سنتری کو ترجیح دیتی ہے۔ خوش قسمتی سے، اس کے ہم جماعتوں نے سختی سے نافذ کردہ زر مبادلہ کی شرحوں کے ساتھ پھلوں کی تجارت کا ایک صحت مند نظام تیار کیا ہے: ایک سیب چھوڑ دو، کہو، اور آپ ایک کیلا حاصل کر سکتے ہیں۔ کیا ایلس کیلے یا کینٹالوپس کو اٹھا کر اور اتار کر تجارت کا ایک سلسلہ انجام دے سکتی ہے، جو اسے اس کے پسندیدہ پھل تک پہنچاتی ہے؟

یہ کافی آسان لگتا ہے۔ "آپ پرائمری اسکول جا سکتے ہیں اور بچوں کو بتا سکتے ہیں،" کہا کرسٹوف ہاس، آکسفورڈ یونیورسٹی میں کمپیوٹر سائنس دان۔ "لوگ سوچیں گے، 'یہ آسان ہونا چاہیے۔'

لیکن ایلس کے مخمصے میں بنیادی ریاضی کا مسئلہ - جسے ویکٹر کے اضافے کے نظام کے لیے قابل رسائی مسئلہ کہا جاتا ہے - حیرت انگیز طور پر لطیف ہے۔ اگرچہ کچھ معاملات آسانی سے حل کیے جاسکتے ہیں، کمپیوٹر سائنسدانوں نے تقریباً نصف صدی تک اس مسئلے کی جامع تفہیم تیار کرنے کے لیے جدوجہد کی۔ اب، پچھلے کچھ سالوں میں ہونے والی کامیابیوں کے سلسلے میں، انہوں نے یہ ثابت کر دیا ہے کہ یہ مسئلہ کتنا پیچیدہ ہو سکتا ہے۔

اس سے پتہ چلتا ہے کہ یہ بچوں جیسا مسئلہ مضحکہ خیز ہے، تقریباً کارٹونی طور پر پیچیدہ - اتنا پیچیدہ کہ عملی طور پر دیگر تمام مشہور مشکل کمپیوٹیشنل مسائل بچوں کے کھیل کی طرح نظر آتے ہیں۔ اس مسئلے کو حل کرنے کے لیے درکار کوششوں کا اندازہ لگانے کی کوشش کریں، اور جلد ہی آپ کو اتنی بڑی تعداد کا سامنا کرنا پڑے گا کہ ان کے ہندسوں کو گننے سے بھی آپ ان نمبروں تک پہنچ جائیں گے جن کے بارے میں آپ نے کبھی نہیں سنا ہوگا۔ اس طرح کی تعداد اکثر کائنات کے پیمانے سے موازنہ کی دعوت دیتی ہے، لیکن وہ مشابہتیں بھی کم ہوتی ہیں۔ "اس سے انصاف نہیں ہوگا،" کہا جارج زیٹشےکیزرسلاؤٹرن، جرمنی میں میکس پلانک انسٹی ٹیوٹ برائے سافٹ ویئر سسٹمز میں کمپیوٹر سائنسدان۔ "کائنات بہت چھوٹی ہے۔"

پہنچ میں؟

اس کے جوہر سے ہٹ کر، قابل رسائی مسئلہ ریاضیاتی اشیاء کے بارے میں ہے جنہیں ویکٹر کہتے ہیں، جن کو نمبروں کی فہرست ترتیب دی جاتی ہے۔ ان فہرستوں میں اندراجات کو اجزاء کہا جاتا ہے، اور ویکٹر میں اجزاء کی تعداد کو اس کی جہت کہا جاتا ہے۔ مثال کے طور پر ایلس کی پھلوں کی فہرست کو چار جہتی ویکٹر (a, b, c, d), جس کے اجزاء اس بات کی نمائندگی کرتے ہیں کہ اس کے پاس کسی بھی وقت کتنے سیب، کیلے، کینٹالوپس اور سنترے ہیں۔

ایک ویکٹر اضافی نظام، یا VAS، ایک نظام میں ریاستوں کے درمیان ممکنہ ٹرانزیشن کی نمائندگی کرنے والے ویکٹرز کا مجموعہ ہے۔ ایلس کے لیے، ٹرانزیشن ویکٹر (−1, −1, 1, 0) کینٹالوپ کے لیے ایک سیب اور کیلے کے تبادلے کی نمائندگی کرے گا۔ VAS قابل رسائی مسئلہ یہ پوچھتا ہے کہ کیا اجازت شدہ ٹرانزیشنز کا کوئی ایسا مجموعہ ہے جو آپ کو ایک مخصوص ابتدائی حالت سے مخصوص ہدف کی حالت میں لے جا سکتا ہے — یا، ریاضی کے لحاظ سے، آیا ٹرانزیشن ویکٹر کا کوئی مجموعہ ہے جو شروع ہونے والے ویکٹر کو ٹارگٹ ویکٹر میں تبدیل کرتا ہے۔ صرف ایک کیچ ہے: نظام کی حالت کو بیان کرنے والے ویکٹر کا کوئی بھی جزو صفر سے نیچے نہیں گر سکتا۔

"یہ حقیقت کے ماڈل کے لیے ایک بہت فطری پابندی ہے،" نے کہا Wojciech Czerwiński، وارسا یونیورسٹی میں کمپیوٹر سائنس دان۔ "آپ کے پاس سیب کی منفی تعداد نہیں ہوسکتی ہے۔"

کچھ نظاموں میں، یہ تعین کرنا آسان ہے کہ آیا ہدف ویکٹر تک رسائی ممکن ہے۔ لیکن ہمیشہ ایسا نہیں ہوتا۔ کمپیوٹر سائنس دان سادہ نظر آنے والے ویکٹر کے اضافے کے نظام میں سب سے زیادہ دلچسپی رکھتے ہیں جس میں یہ واضح نہیں ہے کہ رسائی کا تعین کرنا کتنا مشکل ہے۔ ان معاملات کا مطالعہ کرنے کے لیے، محققین ایک ایسے نمبر کی وضاحت کرتے ہوئے شروع کرتے ہیں جو ایک دیئے گئے نظام کے سائز کی مقدار کا تعین کرتا ہے۔ یہ نمبر، جس کی نمائندگی کرتا ہے۔ n, طول و عرض کی تعداد، ٹرانزیشنز کی تعداد، اور دیگر عوامل پر مشتمل ہے۔ اس کے بعد وہ پوچھتے ہیں کہ رسائی کے مسئلے کی مشکل کتنی جلدی بڑھ سکتی ہے۔ n بڑا ہوتا ہے.

اس سوال کا جواب دینے کے لیے، محققین دو تکمیلی طریقوں کا استعمال کرتے ہیں۔ سب سے پہلے، وہ خاص طور پر مشکل ویکٹر کے اضافے کے نظام کی مثالیں تلاش کرتے ہیں جن میں قابل رسائی کا تعین کرنے کے لیے کچھ کم از کم کوشش کی ضرورت ہوتی ہے۔ ان کم از کم سطحوں کو مسئلے کی پیچیدگی پر "نچلی حد" کہا جاتا ہے - وہ محققین سے کہتے ہیں، "دیئے گئے سب سے مشکل نظام n کم از کم اتنا مشکل ہے۔"

دوسرا، محققین "اوپری حدود" قائم کرنے کی کوشش کرتے ہیں - اس بات کی حدیں کہ کس حد تک رسائی ممکن ہے، حتیٰ کہ انتہائی شیطانی نظاموں میں بھی۔ یہ کہتے ہیں، "دیئے گئے سب سے مشکل واقعات n زیادہ سے زیادہ یہ مشکل ہیں۔" مشکل ترین نظاموں میں درست رسائی کتنی مشکل ہے اس کا تعین کرنے کے لیے، محققین نچلی حدوں کو اوپر اور اوپری باؤنڈز کو نیچے دھکیلنے کی کوشش کرتے ہیں جب تک کہ وہ مل نہ جائیں۔

خوابوں کا سامان

ویکٹر کے اضافے کے نظام کی ایک طویل تاریخ ہے۔ 1960 کی دہائی سے، کمپیوٹر سائنس دانوں نے ان کا استعمال ایسے پروگراموں کو ماڈل بنانے کے لیے کیا ہے جو ایک کمپیوٹیشن کو بہت سے چھوٹے ٹکڑوں میں تقسیم کرتے ہیں اور ان ٹکڑوں پر بیک وقت کام کرتے ہیں۔ اس قسم کی "کنکرنٹ کمپیوٹنگ" اب ہر جگہ موجود ہے، لیکن محققین ابھی تک اس کی ریاضیاتی بنیادوں کو پوری طرح سے نہیں سمجھتے ہیں۔

1976 میں کمپیوٹر سائنسدان رچرڈ لپٹن VAS تک رسائی کے مسئلے کی پیچیدگی کو سمجھنے کی طرف پہلا قدم اٹھایا۔ اس نے نظاموں کی تعمیر کے لیے ایک طریقہ کار تیار کیا جس میں اس بات کا تعین کرنے کا تیز ترین طریقہ یہ ہے کہ آیا ایک ریاست دوسری ریاست سے قابل رسائی ہے یا نہیں ان کے درمیان منتقلی کی ترتیب کو نقشہ بنانا ہے۔ اس نے اسے قابل رسائی مسئلہ کی مشکل کی پیمائش کے طور پر دو احتیاط سے منتخب ریاستوں کے درمیان مختصر ترین راستے کی لمبائی کا استعمال کرنے کی اجازت دی۔

لپٹن پھر ثابت ہوا وہ سائز کا ایک نظام بنا سکتا ہے۔ n جس میں دو ریاستوں کے درمیان مختصر ترین راستے میں $لیٹیکس 2^{2^n}$ سے زیادہ ٹرانزیشن شامل ہیں۔ اس کا مطلب اس کے سسٹمز میں قابل رسائی کا تعین کرنے کے لیے درکار کوششوں پر اسی طرح کے دوہری کفایتی نچلے درجے کا ہے۔ یہ ایک چونکا دینے والی دریافت تھی - دوہری تیز رفتار ترقی کمپیوٹر سائنسدانوں کے ڈراؤنے خوابوں کا سامان ہے۔ درحقیقت، محققین اکثر عام تیز رفتار نمو پر بھی جھک جاتے ہیں، جو کہ اس کے مقابلے میں ہلکا ہوتا ہے: $لیٹیکس {2^5}= 32$، لیکن $لیٹیکس 2^{2^5}$ 4 بلین سے زیادہ ہے۔

زیادہ تر محققین کا خیال تھا کہ لپٹن نے سب سے پیچیدہ ممکنہ ویکٹر کے اضافے کے نظام کو تیار کر لیا ہے، یعنی اس نے نچلی حد کو اتنا ہی اونچا کر دیا ہے جتنا یہ جا سکتا ہے۔ صرف ایک چیز غائب ہے، اس صورت میں، اس کے ساتھ جانے کا ایک اوپری پابند ہوگا - یعنی اس بات کا ثبوت کہ کوئی ایسا نظام نہیں ہو سکتا جس میں قابل رسائی کا تعین کرنا اس سے بھی مشکل ہو۔ لیکن کوئی نہیں جانتا تھا کہ اسے کیسے ثابت کیا جائے۔ کمپیوٹر سائنس دان ارنسٹ مائر اس وقت سب سے قریب آیا جب وہ ثابت ہوا 1981 میں کہ یہ ہمیشہ ممکن ہے، اصولی طور پر، کسی بھی ویکٹر کے اضافے کے نظام میں رسائی کا تعین کرنا۔ لیکن اس کے ثبوت نے کوئی مقداری اوپری پابند نہیں کیا کہ مسئلہ کتنا مشکل ہوسکتا ہے۔ ایک منزل تھی، لیکن کوئی چھت نظر نہیں آتی تھی۔

لپٹن نے کہا ، "میں نے یقینی طور پر اس کے بارے میں سوچا تھا۔ "لیکن تھوڑی دیر کے بعد میں نے ہار مان لی، اور جہاں تک میں بتا سکتا تھا کہ 40 سال کی طرح کسی نے بھی کوئی پیش رفت نہیں کی۔"

2015 میں، کمپیوٹر سائنسدانوں جیروم لیروکس اور سلوین شمٹز آخر میں قائم ایک مقداری اوپری حد - ایک اتنا اونچا کہ محققین نے فرض کیا کہ یہ صرف ایک پہلا قدم ہے جسے لپٹن کی نچلی حد کو پورا کرنے کے لیے نیچے دھکیلا جا سکتا ہے۔

لیکن ایسا نہیں ہوا۔ 2019 میں، محققین نے کئی دہائیوں کی روایتی حکمت کو برقرار رکھتے ہوئے لپٹن کے مقابلے میں ایک نچلی حد کو دریافت کیا۔ VAS تک رسائی کا مسئلہ اس سے کہیں زیادہ پیچیدہ تھا جس کی کسی نے توقع کی تھی۔

طاقتوں کا ایک مینار

2019 کا چونکا دینے والا نتیجہ ناکامی سے نکلا۔ 2018 میں، Czerwiński نے Leroux and فلپ مازوویکی، جو اب وارسا یونیورسٹی میں کمپیوٹر سائنسدان ہیں، اس سے متعلقہ مسئلے پر پیش رفت کرنے میں مدد ملے گی۔ بعد میں ہونے والی بات چیت میں، محققین نے اضافی پیچیدہ ویکٹر کے اضافے کے نظام کی تعمیر کے لیے ایک امید افزا نئے طریقے پر زور دیا، جو VAS تک رسائی کے مسئلے پر ایک نئی نچلی حد کا اشارہ دے سکتا ہے، جہاں ترقی اتنے عرصے سے رکی ہوئی تھی۔

"میرے ذہن میں ہر چیز VAS کی رسائی سے منسلک ہے،" Czerwiński نے یاد کیا۔ ہلکے تدریسی بوجھ کے ساتھ ایک سمسٹر کے دوران، اس نے Leroux، Mazowiecki اور دو دیگر محققین کے ساتھ مل کر خصوصی طور پر اس مسئلے پر توجہ مرکوز کرنے کا فیصلہ کیا۔ سلوومیر لاسوٹا وارسا یونیورسٹی کے اور رینکو لازیچ واروک یونیورسٹی کے

چند مہینوں کے بعد ان کی کوششیں رنگ لائیں ۔ Czerwiński اور ان کے ساتھی demonstrated,en کہ وہ ویکٹر کے اضافے کے نظام بنا سکتے ہیں جس میں دو ریاستوں کے درمیان مختصر ترین راستہ نظام کے سائز سے متعلق تھا ٹیٹریشن نامی ریاضیاتی آپریشن کے ذریعے جس سے خوفناک دوہری ایکسپونیشنل نمو بھی کم دکھائی دیتی ہے۔

ٹیٹریشن ایک پیٹرن کی سیدھی توسیع ہے جو ریاضی میں سب سے زیادہ مانوس کارروائیوں کو جوڑتا ہے، جس کا آغاز اضافہ سے ہوتا ہے۔ ایک ساتھ شامل کریں۔ n ایک عدد کی کاپیاں، اور نتیجہ اس نمبر کو ضرب دینے کے مترادف ہے۔ n. اگر آپ مل کر ضرب لگائیں۔ n کسی نمبر کی کاپیاں، جو کہ کفارہ کے برابر ہے، یا نمبر کو بڑھا کر nطاقت. ٹیٹریشن، جس کی نمائندگی اکثر تیروں کے ایک جوڑے کے ذریعے کی جاتی ہے، اس ترتیب کا اگلا مرحلہ ہے: کسی نمبر کو بذریعہ ٹیٹریٹنگ n اس کا مطلب بیان کرنا n طاقتوں کا مینار پیدا کرنے کے اوقات n کہانیاں اعلی

اپنے سر کو لپیٹنا مشکل ہے کہ ٹیٹریشن کتنی جلدی ہاتھ سے نکل جاتا ہے: $latex 2 uparrowuparrow 3$، یا $latex 2^{2^2}$، 16 ہے، $latex 2 uparrowuparrow 4$ صرف 65,000 سے زیادہ ہے، اور $latex 2 uparrowuparrow 5$ تقریباً 20,000 ہندسوں کے ساتھ ایک عدد ہے۔ $latex 2 uparrowuparrow 6$ کے تمام ہندسوں کو لکھنا جسمانی طور پر ناممکن ہے - اتنی چھوٹی کائنات میں رہنے کی ذمہ داری۔

اپنے تاریخی نتائج میں، Czerwiński اور ان کے ساتھیوں نے ثابت کیا کہ سائز کے ویکٹر کے اضافے کے نظام موجود ہیں۔ n جہاں قابل رسائی کا تعین کرنے کا بہترین طریقہ یہ ہے کہ ایک ایسے راستے کا نقشہ تیار کیا جائے جس میں $latex 2 uparrowuparrow n$ سے زیادہ ٹرانزیشن شامل ہوں، جس سے لپٹن کو بونا کرنے والی ایک نئی لوئر باؤنڈ کا مطلب ہو۔ لیکن جیسا کہ ٹیٹریشن ہے، یہ ابھی تک مسئلہ کی پیچیدگی پر حتمی لفظ نہیں تھا۔

Quinquagintilion اور اس سے آگے 

VAS تک رسائی کی پیچیدگی پر چونکا دینے والے نئے نچلے حصے کے صرف چند ماہ بعد، Leroux اور Schmitz نیچے دھکیل دیا اوپری حد انہوں نے تین سال پہلے قائم کی تھی، لیکن وہ ٹیٹریشن تک پوری طرح نہیں پہنچ پائے۔ اس کے بجائے، انہوں نے ثابت کیا کہ رسائ کے مسئلے کی پیچیدگی ایک ریاضی کے عفریت سے زیادہ تیزی سے نہیں بڑھ سکتی جسے Ackermann فنکشن کہا جاتا ہے۔

اس فنکشن کو سمجھنے کے لیے، ٹیٹریشن کی وضاحت کرنے کے لیے استعمال ہونے والے پیٹرن کو اس کے سنگین نتیجے تک لے جائیں۔ ترتیب میں اگلا آپریشن، جسے پینٹیشن کہتے ہیں، بار بار ٹیٹریشن کی نمائندگی کرتا ہے۔ اس کے بعد بار بار پینٹیشن کے لیے ایک اور آپریشن (ہیکسیشن) ہوتا ہے، وغیرہ۔

Ackermann فنکشن، جس کو $latex A(n)$ کہا جاتا ہے، وہ ہوتا ہے جب آپ نمبر لائن پر ہر اسٹاپ کے ساتھ آپریشنز کی اس سیڑھی کو ایک قدم اوپر لے جاتے ہیں: $latex A(1) = 1 + 1$، $latex A (2) = 2 × 2$، $latex A(3) = 3^3$، $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$، وغیرہ۔ $latex A(4)$ میں ہندسوں کی تعداد بذات خود ایک بہت بڑا نمبر ہے جو تقریباً 1 کوئنکواگینٹلین کے برابر ہے — یہ ایک سنکی اور شاذ و نادر ہی ضروری نام ہے جس کے بعد 1 صفر ہوتے ہیں۔ "153 کے Ackermann کے بارے میں فکر مت کرو،" مشورہ دیا جیویر ایسپارزا، میونخ کی ٹیکنیکل یونیورسٹی میں کمپیوٹر سائنس دان۔

لیروکس اور شمٹز کے نتیجے نے نچلے اور اوپری حدود کے درمیان ایک بڑا فاصلہ چھوڑ دیا — VAS تک رسائی کے مسئلے کی قطعی پیچیدگی حد کے یا تو سرے پر یا درمیان میں کہیں بھی ہوسکتی ہے۔ Czerwiński کا ارادہ نہیں تھا کہ وہ اس خلا کو کھڑا ہونے دیں۔ "ہم اس پر کام کرتے رہے کیونکہ یہ واضح تھا کہ یہ ہماری زندگی میں اب تک کی سب سے بڑی چیز ہے،" انہوں نے کہا۔

حتمی پیش رفت 2021 میں ہوئی، جب Czerwiński Łukasz Orlikowski نامی دوسرے سال کے انڈرگریجویٹ طالب علم کو مشورہ دے رہا تھا۔ اس نے Orlikowski کو اس مسئلے کی ایک سادہ شکل تفویض کی تاکہ اسے تیز رفتاری سے آگے بڑھایا جا سکے، اور Orlikowski کے کام نے ان دونوں کو ایک نئی تکنیک تیار کرنے میں مدد کی جو عام رسائی کے مسئلے پر بھی لاگو ہوتی ہے۔ جس نے انہیں اجازت دی۔ نچلی حد کو بلند کریں۔ کافی حد تک - لیروکس اور شمٹز کے ایکرمین کے اوپری باؤنڈ تک۔ آزادانہ طور پر کام کرنا، Leroux حاصل کیا ایک مساوی نتیجہ اسی وقت کے ارد گرد.

آخر کار، محققین نے قابل رسائی مسئلہ کی حقیقی پیچیدگی کو ختم کر دیا تھا۔ Czerwiński، Orlikowski اور Leroux کی نچلی حد سے پتہ چلتا ہے کہ بتدریج بڑے ویکٹر اضافی نظاموں کا ایک سلسلہ ہے جس میں دو ریاستوں کے درمیان مختصر ترین راستہ Ackermann فنکشن کے تناسب سے بڑھتا ہے۔ لیروکس اور شمٹز کے اوپری باؤنڈ نے ظاہر کیا کہ رسائ کا مسئلہ اس سے زیادہ پیچیدہ نہیں ہو سکتا - اس کو حل کرنے کے لیے ایک ناقابل عمل عملی طریقہ کار کی امید رکھنے والے کسی کے لیے بہت کم تسلی۔ یہ اس بات کی ایک حیرت انگیز مثال ہے کہ بظاہر سادہ کمپیوٹیشنل مسائل کتنے لطیف ہو سکتے ہیں۔

کبھی ختم نہیں ہوا۔

محققین نے اس کی درست پیچیدگی کا تعین کرنے کے بعد VAS تک رسائی کے مسئلے کا مطالعہ جاری رکھا ہے، کیونکہ سوال کی بہت سی قسمیں ابھی تک جواب طلب ہیں۔ Ackermann اوپری اور نچلی حدیں، مثال کے طور پر، بڑھانے کے مختلف طریقوں کے درمیان فرق نہیں کرتے n, جیسے ویکٹر کی جہت میں اضافہ یا اجازت شدہ ٹرانزیشن کی تعداد میں اضافہ۔

حال ہی میں، Czerwiński اور ان کے ساتھیوں نے ترقی کی متعین جہت کے ساتھ ویکٹر کے اضافے کے نظام کی مختلف حالتوں میں کتنی جلدی پیچیدگی بڑھ سکتی ہے اس کا مطالعہ کرکے ان الگ الگ اثرات کو چھیڑنا۔ لیکن مزید کام کرنا باقی ہے — یہاں تک کہ تین جہتوں میں بھی، جہاں ویکٹر کے اضافے کے نظام کو تصور کرنا آسان ہے، رسائی کے مسئلے کی صحیح پیچیدگی نامعلوم ہے۔

"ایک طرح سے، یہ ہمارے لیے شرمناک ہے،" مازوئیکی نے کہا۔

محققین کو امید ہے کہ نسبتاً آسان کیسز کی بہتر تفہیم ان کو کمپیوٹیشن کے دوسرے ماڈلز کا مطالعہ کرنے کے لیے نئے ٹولز تیار کرنے میں مدد کرے گی جو کہ ویکٹر کے اضافے کے نظام سے زیادہ وسیع ہیں۔ فی الحال، ہم ان مزید وسیع ماڈلز کے بارے میں تقریباً کچھ نہیں جانتے ہیں۔

Zetzsche نے کہا، "میں اسے کمپیوٹیبلٹی کو سمجھنے کی ایک بہت ہی بنیادی جدوجہد کے حصے کے طور پر دیکھتا ہوں۔

Quanta ہمارے سامعین کی بہتر خدمت کے لیے سروے کا ایک سلسلہ کر رہا ہے۔ ہماری لے لو کمپیوٹر سائنس ریڈر سروے اور آپ کو مفت جیتنے کے لیے داخل کیا جائے گا۔ Quanta پنی