جمع ہو کر ہدف بننے والے اعداد چننا، تقریباً انہیں پڑھنے جتنی تیزی سے

یہ ایک ایسی پہیلی ہے جسے کوئی بھی بیان کر سکتا ہے۔ آپ کے پاس پورے اعداد کی ایک فہرست ہے — فرض کریں 3، 9، 14، 20 — اور ایک ہدف، فرض کریں 23۔ کیا آپ ان میں سے کچھ ایسے چن سکتے ہیں کہ ان کا مجموعہ ٹھیک ہدف کے برابر ہو؟ (یہاں ہاں: 3 + 20 یا 9 + 14۔) یہ Subset Sum (ذیلی مجموعے کا حاصل جمع) ہے، کمپیوٹر سائنس کے سب سے بنیادی مسائل میں سے ایک۔ مقالہ اسے ایک بنیادی NP-مکمل مسئلہ قرار دیتا ہے، یعنی مسائل کا ایک خاندان جو ٹھیک ٹھیک حل کرنے میں مشکل کے لیے مشہور ہے۔

البتہ ایک چور دروازہ موجود ہے۔ اگر اعداد بہت بڑے نہ ہوں تو چالاک الگورتھم ایسے وقت میں چلتے ہیں جو ان کی جسامت پر منحصر ہو۔ کلاسیکی طریقہ، جو 1957 میں بیلمین کا ہے، اعداد کی تعداد n ضرب ہدف t کے متناسب وقت لیتا ہے۔ تب سے الگورتھم بہتر ہوتے رہے ہیں:

• پیسنگر (1999): n × N کے متناسب، جہاں N سب سے بڑا عدد ہے؛
• برنگمین (2017): تقریباً n + t؛
• کئی ٹیمیں (2021–2024): تقریباً n + N^(5/3)، پھر n + N^(3/2)۔

مقدس منزل تقریباً n + N کا وقت تھا — ان پٹ پڑھنے سے کچھ زیادہ نہیں۔ اس شعبے کے محققین نے اسے اس سلسلۂ کار کا “سب سے اہم حل طلب مسئلہ” کہا تھا۔

منزل سے بال برابر فاصلے پر

چین کی ژے جیانگ یونیورسٹی کے لن چن، یوچن ماؤ اور گوچوان ژانگ ایک ایسا الگورتھم پیش کرتے ہیں جو n + N^(1+ε) وقت میں چلتا ہے، جہاں ε پہلے سے مقرر کیا گیا کوئی بھی چھوٹا مثبت عدد ہو سکتا ہے — 0.1، 0.01، 0.001۔ یہ متعین (deterministic) ہے، منفی اعداد اور دہرائی گئی قدریں قبول کرتا ہے، اور ایک ریاضیاتی ثبوت کے ساتھ آتا ہے۔ مصنفین اس وقت کو تقریباً بہترین (near-optimal) کہتے ہیں۔

نتیجہ سمتیوں تک پھیلتا ہے: اشیا اس طرح چننا کہ کئی مجموعے بیک وقت اپنے اہداف تک پہنچیں، d محددات کے لیے N^(d+ε) وقت کے ساتھ۔ یہ بدلے میں کئی گروہوں کے اٹھائے گئے عدد صحیح پروگرامنگ (integer programming) کے ایک سوال کا جزوی جواب دیتا ہے — ایسی مساواتوں کے نظاموں کے پورے اعداد والے حل تلاش کرنا جن کے متغیرات محدود ہوں۔ دو نتائج واضح طور پر نکالے گئے ہیں: اعداد کے ایک مجموعے کو دو برابر حصوں میں بانٹنا، اور دو یکساں مشینوں کے درمیان کام زیادہ سے زیادہ برابری سے تقسیم کرنا۔

اعداد کو بلند تر بعد میں اٹھانا

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

ان کی مثال مجموعہ {11, 12, 22, 24} ہے۔ 11 اور 22 کو پہلے محور کے ساتھ ایک قدم اور دو قدم کے طور پر لکھیں، اور 12 اور 24 کو دوسرے محور کے ساتھ ایک قدم اور دو قدم کے طور پر۔ تب ممکنہ مجموعے 4 ضرب 4 کے ایک چھوٹے مربع کے ہر نقطے کو بھر دیتے ہیں۔ لیکن اس مربع کو واپس ایک لکیر پر دبا دیں — 11x + 12y کا حساب کر کے — تو مجموعے 0 اور 69 کے درمیان بکھرے ہوئے سات الگ جھرمٹ بناتے ہیں جن کے درمیان خلا ہیں۔ یہ خلا تخمین (projection) کا دھوکا ہیں؛ دو ابعاد میں ساخت سادہ ہے۔

الگورتھم جمعی مجموعیات (additive combinatorics) کے نتائج استعمال کرتے ہوئے کسی بھی ان پٹ کے لیے ایسے بلند تر بعدی محددات بناتا ہے۔ “بھرے ہوئے” علاقے کے اندر جواب مفت میں مل جاتے ہیں۔ صرف کنارے کے قریب ایک باریک پٹی کو حقیقی محنت درکار ہے، جسے الگورتھم چھوٹے مسائل میں توڑ کر تکراری (recursive) طور پر حل کرتا ہے۔ ہر دور اس پٹی کو تیزی سے سکیڑتا ہے، اور کبھی بھی صرف ایک مستقل تعداد میں نئے ابعاد شامل کیے جاتے ہیں۔

ثبوت کیسے بنا

مقالہ ایک “مصنوعی ذہانت سے متعلق انتباہ” سے شروع ہوتا ہے۔ مصنفین نے ثبوت کا بنیادی راستہ خود وضع کیا، جو مسئلے کے گھنے، کثیر بعدی روپوں پر ان کے اپنے حالیہ کام پر مبنی ہے۔ پھر انہوں نے ایک مصنوعی ذہانت ماڈل، GPT Astra Ultra، کو ان خیالات کو مکمل ریاضیاتی ثبوتوں میں بدلنے کے لیے استعمال کیا۔ یہ کئی ذیلی قضیوں (lemmas) پر اٹک گیا، جو مصنفین کے خیالات سے حل ہوئے؛ ایک عوامی تحقیقی نوٹ ان گفتگوؤں کو دستاویزی شکل دیتا ہے۔ جب بنیادی بے ترتیب (randomised) الگورتھم مکمل ہو گیا تو ماڈل نے اسے متعین اور کثیر بعدی روپوں تک “مصنفین کی کسی رہنمائی کے بغیر” وسعت دی۔ ماڈل نے مقالے کا مسودہ بھی تیار کیا اور، مصنفین لکھتے ہیں، Lean 4 ثبوت معاون میں ایک ثبوت کے ذریعے اس کے بنیادی نتائج کی تصدیق کی۔ مصنفین مواد کی پوری ذمہ داری لیتے ہیں۔

ابھی پوری طرح اختتامی لکیر نہیں

قوت نما ٹھیک 1 کے بجائے 1 + ε ہے، اور چھپے ہوئے مستقلات ε کے چھوٹا ہونے کے ساتھ بڑھتے ہیں؛ ابعاد کی تعداد پر انحصار بہتر نہیں بنایا گیا۔ مصنفین خود الگورتھم کو “کافی پیچیدہ” قرار دیتے ہیں۔ مقالہ نظریاتی ہے: یہ کسی عملی نفاذ یا کارکردگی کی جانچ کی اطلاع نہیں دیتا۔