کمپیوٹر سائنس میں 1962 کی ایک رکاوٹ ٹوٹ گئی

ہیملٹونین چکر (Hamiltonian cycle) کسی جال میں ایسا آنے جانے کا سفر ہے جو ہر نقطے پر ٹھیک ایک بار جاتا ہے اور شروع کے مقام پر واپس آ جاتا ہے۔ ایک سمت دار (directed) جال میں ہر ربط ایک تیر ہوتا ہے جس پر صرف ایک ہی سمت میں چلا جا سکتا ہے، جیسے یک طرفہ سڑک۔ اس مسئلے کی وزن دار شکل غیر متشاکل ٹریولنگ سیلزمین مسئلہ (asymmetric travelling salesman problem) ہے۔

یہ طے کرنا کہ آیا ایسا چکر موجود ہے، درسی کتابوں کا ایک مشکل مسئلہ ہے۔ 1962 میں رچرڈ بیلمین نے، اور ان سے آزادانہ طور پر مائیکل ہیلڈ اور رچرڈ کارپ نے، ڈائنامک پروگرامنگ کے ایسے الگورتھم پیش کیے جو n نقطوں کے جال کے لیے اسے تقریباً 2ⁿ وقت میں حل کرتے ہیں (ان عوامل کو چھوڑ کر جو صرف کثیر رقمی (polynomial) انداز میں بڑھتے ہیں)۔ ساٹھ سال سے زیادہ عرصے تک کوئی بھی عمومی سمت دار جالوں پر بنیادی طور پر اس سے بہتر نہیں کر سکا۔

غیر سمت دار رشتے دار پہلے ہی گر چکا تھا

دو طرفہ روابط والے جالوں کے لیے آندریاس بیورکلنڈ نے 2014 میں ایک بے ترتیب الگورتھم کے ذریعے یہ رکاوٹ توڑی جو 1.657ⁿ میں چلتا ہے؛ مقالے کے مطابق اس کام پر انہیں 2016 کا EATCS–IPEC نیروڈ انعام ملا۔ یہ آج بھی عمومی غیر سمت دار جالوں کے لیے معلوم تیز ترین الگورتھم ہے۔ سمت دار جالوں کے لیے پیش رفت صرف خاص صورتوں میں ہوئی — دو حصوں والے (bipartite) جال، فی نقطہ کم روابط والے جال — یا ایک غیر ثابت شدہ مفروضے کے تحت، یعنی اسٹراسن کے مقاربی رینک کے قیاس (asymptotic rank conjecture) کے تحت۔

نئی حد

یونیورسٹی آف ٹوکیو کے توموہیرو کوآنا اور ٹوکیو کی کمپنی CyberAgent کے سو کومابے اب ایک بے ترتیب الگورتھم پیش کرتے ہیں جو سمت دار مسئلے کا فیصلہ اتنے وقت میں کرتا ہے:

O((375/196)ⁿ) = O(1.9133ⁿ)**۔

عمومی سمت دار جالوں کے لیے یہ 1962 کے بعد قوت نما فعل کی اساس (base) میں پہلی بہتری ہے۔

طاق اور جفت میں گنتی

مشکل باریک ہے۔ چکروں کو ماڈیولو 2 گننا — یعنی صرف یہ جاننا کہ ان کی تعداد طاق ہے یا جفت — پہلے ہی 2ⁿ سے کم وقت میں ممکن تھا۔ لیکن چکروں کی جفت، غیر صفر تعداد بالکل صفر جیسی دکھائی دیتی ہے۔ کلاسیکی حل یہ ہے کہ روابط کو بے ترتیب وزن دیے جائیں تاکہ کسی کل وزن پر ایک حل منفرد ہو جائے (علیحدگی کا لیما، isolation lemma)؛ لیکن جفت-طاق گننے کا تیز طریقہ وزن نہیں سنبھال سکتا تھا۔

مصنفین کا نسخہ، سادہ الفاظ میں:

چکر کے ایک تیر کا اندازہ لگاؤ، اور اس کے بجائے ایسا راستہ ڈھونڈو جو اس تیر کے ایک سرے سے دوسرے سرے تک ہر نقطے سے گزرے۔
ہر تیر کو 1/50 کے امکان کے ساتھ بے ترتیب طور پر مٹا دو۔
ہر نقطے پر آنے والے تیروں کے تین گروہ بناؤ، اور بچ جانے والے ہر تیر کو گروہوں کے کسی بے ترتیب، غیر خالی مجموعے میں نقل کر دو۔
اگر چکر موجود ہے، تو کم از کم (49/50)ⁿ⁻¹ کے امکان کے ساتھ ہر نقطے کے لیے ایک گروہ اس طرح چنا جا سکتا ہے کہ درست راستوں کی تعداد طاق ہو۔
ہر گروہ کو — ہر تیر کو نہیں — ایک بے ترتیب وزن دو۔ اب علیحدگی کی ترکیب کام کرتی ہے، اور تقریباً (50/49)ⁿ بار دہرانا کافی ہے۔
ہر بار دہرانے میں، (15/8)ⁿ وقت میں ہر کل وزن پر طاق یا جفت گنتی نکالی جاتی ہے، جس کے لیے بیورکلنڈ، کاسکی اور کوٹس کے میٹرکس ڈیٹرمیننٹس کے مجموعے اور ایک بے ترتیب “لکیری کاری” (linearisation) استعمال ہوتی ہے جو اروند اور گروسوامی نے بھی استعمال کی تھی۔

دونوں کو ضرب دو: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ۔

مشین کا تیار کردہ ثبوت

مقالہ تخلیقی مصنوعی ذہانت کے بارے میں ایک اعلان پر ختم ہوتا ہے: ChatGPT 6 Astra نے مرکزی مسئلے (theorem) کا ثبوت تیار کیا اور مسودہ لکھنے میں مدد کی۔ مصنفین نے درمیانی قضیوں (propositions) کے بیانات فراہم کیے، جو ماڈل کے اصل حل کی ایک ترکیبیاتی (combinatorial) تشریح پیش کرتے ہیں، پھر سب کچھ جانچا، اس پر نظرثانی کی، اور پوری ذمہ داری قبول کرتے ہیں۔

نتیجہ نظریاتی ہے — کوئی پروگرام نہیں چلایا گیا — اور الگورتھم بے ترتیب ہے، جس میں دونوں طرف غلطی کا تھوڑا سا امکان ہے۔ یک طرفہ سڑکوں کے لیے 1.9133 اور دو طرفہ سڑکوں کے لیے 1.657 کے درمیان اب بھی ایک وسیع خلا کھلا ہے۔