نمبر 15 ایک لامحدود گرڈ کی خفیہ حد کو بیان کرتا ہے۔

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

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

لیکن پھر 2020 میں Subercaseaux کو پیار ہو گیا، اور جیسا کہ اکثر ہوتا ہے، اس کی ترجیحات بدل گئیں۔ اس کے جنون کا مقصد ایک سوال تھا جسے اس نے ایک آن لائن فورم پر دیکھا۔ زیادہ تر مسائل اس نے اسکین کیے اور بھول گئے، لیکن اس نے اس کی آنکھ پکڑ لی۔ اس نے دائیں طرف مڑایا۔

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

سوال نمبروں کے ساتھ لامحدود گرڈ کو بھرنے کے بارے میں تھا۔ ایسا نہیں تھا، جیسا کہ یہ نکلا، جس طرح کا مسئلہ ایک لارک پر حل کرتا ہے۔ ایسا کرنے کے لیے، Subercaseaux کو کارنیگی میلن یونیورسٹی میں گریجویٹ اسکول کے لیے چلی چھوڑنا پڑا۔

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

ہر ممکن طریقہ

2002 میں وین گوڈارڈ کلیمسن یونیورسٹی کے اور کچھ ہم خیال ریاضی دان امتزاج میں مسائل کو تھوک رہے تھے، کچھ رکاوٹوں کے پیش نظر رنگین نقشوں کے بارے میں میدان کے اہم سوالات پر نئے موڑ کے ساتھ آنے کی کوشش کر رہے تھے۔

بالآخر وہ ایک ایسے مسئلے پر اترے جو گرڈ سے شروع ہوتا ہے، جیسے گراف پیپر کی شیٹ جو ہمیشہ کے لیے جاری رہتی ہے۔ مقصد اسے نمبروں سے بھرنا ہے۔ صرف ایک رکاوٹ ہے: ایک ہی نمبر کے ہر ایک واقعہ کے درمیان فاصلہ خود نمبر سے زیادہ ہونا چاہئے۔ (فاصلہ عمودی اور افقی علیحدگی کو ملا کر ماپا جاتا ہے، ایک میٹرک جسے "ٹیکسیب" فاصلہ کہا جاتا ہے جس طرح سے یہ گرڈ شہری سڑکوں پر چلنے سے مشابہت رکھتا ہے۔) 1s کا جوڑا ملحقہ خلیات پر قبضہ نہیں کر سکتا، جس میں ٹیکسی کیب کا فاصلہ 1 ہے، لیکن انہیں براہ راست اخترن خلیوں میں رکھا جا سکتا ہے، جن کا فاصلہ 2 ہے۔

ابتدا میں، گوڈارڈ اور اس کے ساتھی یہ جاننا چاہتے تھے کہ آیا اعداد کے ایک محدود سیٹ سے لامحدود گرڈ کو بھرنا بھی ممکن ہے۔ لیکن اس وقت تک وہ اور اس کے چار ساتھی یہ "پیکنگ کلرنگ" مسئلہ شائع کیا۔ جرنل میں Ars Combinatoria 2008 میں، انہوں نے ثابت کیا تھا کہ اسے 22 نمبروں کے ذریعے حل کیا جا سکتا ہے۔ وہ یہ بھی جانتے تھے کہ اسے صرف پانچ نمبروں سے حل کرنے کا کوئی طریقہ نہیں ہے۔ اس کا مطلب یہ تھا کہ مسئلے کا اصل جواب — مطلوبہ تعداد کی کم از کم تعداد — درمیان میں کہیں موجود ہے۔

محققین نے اصل میں ایک لامحدود گرڈ نہیں بھرا. انہیں نہیں کرنا پڑا۔ اس کے بجائے، گرڈ کا ایک چھوٹا ذیلی سیٹ لینا کافی ہے — کہیے کہ 10 بائی 10 مربع — اسے نمبروں سے پُر کریں، پھر دکھائیں کہ بھرے ہوئے سب سیٹ کی کاپیاں ایک دوسرے کے ساتھ لگائی جا سکتی ہیں، جس طرح سے آپ اسے کور کریں گے۔ ٹائل کی کاپیوں کے ساتھ فرش۔

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

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

جب Subercaseaux CMU میں شروع ہوا اور Heule کو اس کے ساتھ کام کرنے پر راضی کر لیا، تو انہوں نے جلدی سے 15 نمبروں کے ساتھ گرڈ کا احاطہ کرنے کا ایک طریقہ ڈھونڈ لیا۔ وہ صرف 12 نمبروں سے مسئلہ حل ہونے کے امکان کو بھی رد کرنے میں کامیاب رہے۔ لیکن ان کی فتح کے جذبات مختصر وقت کے لیے تھے، کیوں کہ انھوں نے محسوس کیا کہ انھوں نے محض ان نتائج کو دوبارہ پیش کیا ہے جو ایک طویل عرصے سے جاری تھے: 2017 تک، محققین کو معلوم تھا کہ جواب 13 سے کم یا 15 سے زیادہ نہیں تھا۔ .

پہلے سال کے گریڈ کے طالب علم کے لیے جس نے ایک بڑے پروفیسر کو اپنے پالتو جانوروں کے مسئلے پر کام کرنے کے لیے تیار کیا تھا، یہ ایک پریشان کن دریافت تھی۔ "میں گھبرا گیا تھا۔ میں بنیادی طور پر کئی مہینوں سے کسی مسئلے پر اس بات کو سمجھے بغیر کام کر رہا تھا، اور اس سے بھی بدتر، میں نے مارجن کو بنایا تھا۔ اس پر اپنا وقت ضائع کرو! Subercaseaux لکھا ہے ایک بلاگ پوسٹ میں جو ان کے کام کا جائزہ لے رہے ہیں۔

تاہم، ہیول نے ماضی کے نتائج کی دریافت کو متحرک پایا۔ اس نے یہ ظاہر کیا کہ دوسرے محققین نے اس مسئلے کو کام کرنے کے لیے کافی اہم پایا، اور اس کے لیے اس بات کی تصدیق کی کہ حاصل کرنے کا واحد نتیجہ مسئلہ کو مکمل طور پر حل کرنا تھا۔

انہوں نے کہا، "ایک بار جب ہمیں پتہ چلا کہ اس مسئلے پر 20 سال کام ہو چکا ہے، اس نے تصویر کو مکمل طور پر بدل دیا۔"

فحاشی سے بچنا

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

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

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

گوڈارڈ نے کہا کہ "اس وحشیانہ قوت کو کرنے کی کوشش کرنا کائنات کے ختم ہونے تک لے جائے گا اگر آپ نے اسے بے دلی سے کیا،" گوڈارڈ نے کہا۔ "لہذا آپ کو اسے کسی ایسی چیز تک لانے کے لیے کچھ ٹھنڈی آسانیاں درکار ہیں جو ممکن ہے۔"

مزید برآں، جب بھی آپ پیکنگ کلرنگ کے مسئلے میں کوئی نمبر شامل کرتے ہیں، تو یہ تقریباً 100 گنا مشکل ہو جاتا ہے، جس طرح ممکنہ امتزاج کے ضرب لگتے ہیں۔ اس کا مطلب یہ ہے کہ اگر متوازی طور پر کام کرنے والے کمپیوٹرز کا ایک بینک حساب کے ایک دن میں 12 کو مسترد کر سکتا ہے، تو انہیں 100 کو مسترد کرنے کے لیے 13 دن کی گنتی کا وقت درکار ہوگا۔

Heule اور Subercaseaux نے ایک طرح سے بروٹ فورس کمپیوٹیشنل اپروچ کو بیہودہ سمجھا۔ "ہمارے پاس کئی امید افزا خیالات تھے، لہذا ہم نے 'آئیے اپنے نقطہ نظر کو بہتر بنانے کی کوشش کریں جب تک کہ ہم اس مسئلے کو کلسٹر پر 48 گھنٹے سے بھی کم وقت میں حل نہ کر لیں،'" Subercaseaux نے کہا۔

ایسا کرنے کے لیے، انہیں کمپیوٹنگ کلسٹر کو آزمانے والے مجموعوں کی تعداد کو محدود کرنے کے طریقے تلاش کرنے تھے۔

"[وہ] نہ صرف اسے حل کرنا چاہتے ہیں، بلکہ اسے متاثر کن طریقے سے حل کرنا چاہتے ہیں،" کہا الیگزینڈر سوفر کولوراڈو یونیورسٹی، کولوراڈو اسپرنگس کا۔

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

Heule اور Subercaseaux نے ایسے قواعد شامل کیے جن کی مدد سے کمپیوٹر کو ہم آہنگی کے امتزاج کو مساوی سمجھا جاتا ہے، جس سے تلاش کا کل وقت آٹھ کے عنصر سے کم ہوتا ہے۔ انہوں نے ایک تکنیک کو بھی استعمال کیا جو ہیول نے پچھلے کام میں تیار کیا تھا جسے کیوب اور فتح کہا جاتا ہے، جس نے انہیں ایک دوسرے کے ساتھ متوازی طور پر مزید مجموعوں کی جانچ کرنے کی اجازت دی۔ اگر آپ جانتے ہیں کہ دیئے گئے سیل میں 3، 5 یا 7 ہونا ضروری ہے، تو آپ اس مسئلے کو تقسیم کر سکتے ہیں اور کمپیوٹر کے مختلف سیٹوں پر بیک وقت تین امکانات میں سے ہر ایک کی جانچ کر سکتے ہیں۔

جنوری 2022 تک ان بہتریوں نے ہیول اور سبرکاساؤکس کو ایک تجربے میں پیکنگ کلرنگ کے مسئلے کے جواب کے طور پر 13 کو مسترد کرنے کی اجازت دی جس کے لیے کمپیوٹنگ کے دو دن سے بھی کم وقت درکار تھا۔ اس سے ان کے پاس دو ممکنہ جوابات رہ گئے: 14 یا 15۔

ایک بڑا پلس

14 کو مسترد کرنے کے لیے — اور مسئلے کو حل کرنے کے لیے — ہیول اور سبرکاساؤکس کو کمپیوٹر کی تلاش کو تیز کرنے کے لیے اضافی طریقے تلاش کرنے تھے۔

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

انہوں نے اپنے بولین فارمولے کو دوبارہ لکھا تاکہ متعدد متغیر سوالات کی نمائندگی کریں جیسے: کیا اس جمع شکل والے خطے میں کہیں 7 ہے؟ کمپیوٹر کو قطعی طور پر یہ شناخت کرنے کی ضرورت نہیں تھی کہ 7 خطے میں کہاں ہو سکتا ہے۔ اسے صرف اس بات کا تعین کرنے کی ضرورت ہے کہ آیا یہ وہاں تھا یا نہیں - ایک ایسا سوال جس کا جواب دینے کے لیے کافی کم کمپیوٹیشنل وسائل درکار ہیں۔

ہیول نے کہا کہ متغیرات کا ہونا جو مخصوص جگہوں کے بجائے صرف پلسز کے بارے میں بات کرتے ہیں مخصوص خلیات میں ان کے بارے میں بات کرنے سے کہیں زیادہ بہتر ثابت ہوئے۔

پلس سرچ کی کارکردگی کی مدد سے، Heule اور Subercaseaux نے نومبر 14 میں کمپیوٹر کے ایک تجربے میں 2022 کو مسترد کر دیا جس نے 13 کو مسترد کرنے کے مقابلے میں چلانے میں کم وقت لیا۔ کمپیوٹر کا نتیجہ درست تھا - تقریباً اتنا ہی وقت جتنا کہ انہوں نے کمپیوٹر کو اس نتیجے پر پہنچنے کے قابل بنانے میں صرف کیا تھا۔

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

Subercaseaux کے لیے، یہ ان کے تحقیقی کیریئر کی پہلی حقیقی فتح تھی۔ اور اگرچہ یہ اس قسم کی دریافت نہیں ہو سکتی تھی جب اس نے پہلی بار ریاضی میں کام کرنے پر غور کیا تھا، اس نے محسوس کیا کہ آخر میں، اس کے اپنے فکری انعامات تھے۔

"یہ اس فارم کی سمجھ میں نہیں آرہا ہے جہاں آپ مجھے بلیک بورڈ دیتے ہیں اور میں آپ کو دکھا سکتا ہوں کہ یہ 15 کیوں ہے،" اس نے کہا۔ "لیکن ہم نے یہ سمجھ لیا ہے کہ مسئلہ کی رکاوٹیں کس طرح کام کرتی ہیں، یہاں 6 یا وہاں 7 کا ہونا کتنا بہتر ہے۔ ہم نے بہت زیادہ بدیہی سمجھ حاصل کی ہے۔"