جوڑ پورا کرن والے عدد چُننا، لگ بھگ اوہناں نوں پڑھن جنی تیزی نال
ایہہ اک بجھارت اے جو ہر کوئی دس سکدا اے۔ تہاڈے کول پورے عدداں دی اک لسٹ اے — مثلاً 3، 9، 14، 20 — تے اک ٹیچا، مثلاً 23۔ کیہ تسیں اوہناں وچوں کجھ انج چُن سکدے او پئی اوہ ٹھیک ٹیچے تیک جڑن؟ (ایتھے، ہاں: 3 + 20 یا 9 + 14۔) ایہہ اے Subset Sum، کمپیوٹر سائنس دے سبھ توں بنیادی مسئلیاں وچوں اک۔ مقالہ ایہنوں اک بنیادی NP-complete مسئلہ آکھدا اے، مسئلیاں دا اک ٹبر جو ٹھیک ٹھیک حل کرن وچ اوکھا ہون لئی جانیا جاندا اے۔
پر اک چور موری اے۔ جے عدد بہت وڈے نئیں، تے چلاک الگورتھم اجیہے ویلے وچ چلدے نیں جو اوہناں دے سائز اُتے اے۔ بیلمین دا 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) بارے سی — مساواتاں دے اجیہے نظاماں دے پورے عدد والے حل لبھنا جنہاں دے متغیر محدود نیں۔ دو نتیجے کھل کے کڈھے گئے نیں: عدداں دے اک سیٹ نوں دو برابر ادھاں وچ ونڈنا، تے کماں نوں دو اکو جیہیاں مشیناں وچکار جنا ہو سکے برابر ونڈنا۔
عدداں نوں اُچے بُعد وچ چکنا
مکھ خیال جیومیٹری والا اے۔ پہلاں ای پتہ سی پئی مسئلہ سوکھا اے جدوں عدد سنگھنے (dense) ہون تے ٹیچا ممکنہ جوڑاں دی حد دے چنگی طرح اندر ہووے۔ لکھاریاں دا مشاہدہ: عدداں دا اک کھلریا (sparse) سیٹ وی سنگھنا لگ سکدا اے جدوں اوہنوں اُچے بُعد وچ ویکھیا جاوے۔
اوہناں دی مثال سیٹ {11, 12, 22, 24} اے۔ 11 تے 22 نوں پہلے دھرے (axis) اُتے اک قدم تے دو قدم لکھو، تے 12 تے 24 نوں دوجے دھرے اُتے اک قدم تے دو قدم۔ ممکنہ جوڑ فیر اک نکے 4 ضرب 4 چورس دے ہر نقطے نوں بھر دیندے نیں۔ پر اوس چورس نوں واپس اک لکیر اُتے دبا دیو — 11x + 12y کڈھ کے — تے جوڑ ست وکھرے جھنڈ بناؤندے نیں جنہاں وچکار خلا نیں، 0 تے 69 وچکار کھلرے ہوئے۔ خلا پرچھاویں (projection) دا دھوکا نیں؛ دو بُعداں وچ بناوٹ سادی اے۔
الگورتھم ہر ان پٹ لئی اجیہے اُچے بُعدی محدد بناؤندا اے، جوڑی کامبینیٹرکس (additive combinatorics) دے نتیجے ورت کے۔ «بھرے ہوئے» علاقے دے اندر، جواب مفت آؤندے نیں۔ صرف کنڈھے دے نیڑے اک پتلا علاقہ اصلی کم منگدا اے، جیہنوں الگورتھم نکے مسئلیاں وچ توڑ کے دہرائی (recursive) نال حل کردا اے۔ ہر گیڑا اوس علاقے نوں تیزی نال سنگوڑدا اے، تے صرف پکی گنتی دے نویں بُعد ای جوڑے جاندے نیں۔
ثبوت کیویں بنیا
مقالہ اک «AI disclaimer» نال کھلدا اے۔ لکھاریاں نے مکھ ثبوتی راہ آپ بنایا، مسئلے دے سنگھنے، کئی بُعدی روپاں اُتے اپنے نویں کم اُتے اسار کے۔ فیر اوہناں نے ایہناں خیالاں نوں پورے ریاضیاتی ثبوتاں وچ بدلن لئی اک AI ماڈل، GPT Astra Ultra، ورتیا۔ ایہہ کئی لیماں (lemmas) اُتے اڑ گیا، جو لکھاریاں دے خیالاں نال حل ہوئے؛ اک عوامی کھوجی نوٹ گل بات ریکارڈ کردا اے۔ جدوں مڈھلا بے ترتیب (randomised) الگورتھم پورا ہو گیا، ماڈل نے اوہنوں پکے، کئی بُعدی روپاں تیک «لکھاریاں دی کسے رہنمائی توں بنا» ودھایا۔ ماڈل نے مقالے دا خاکہ وی لکھیا تے، لکھاری لکھدے نیں، ایہدے مکھ نتیجیاں دی Lean 4 ثبوتی مددگار وچ اک ثبوت نال تصدیق کیتی۔ لکھاری مواد دی پوری ذمہ داری لیندے نیں۔
ہلے آخری لکیر نئیں
قوت نما (exponent) ٹھیک 1 دی تھاں 1 + ε اے، تے لکے مستقل ε دے گھٹن نال ودھدے نیں؛ بُعداں دی گنتی اُتے انحصار نوں بہتر نئیں بنایا گیا۔ لکھاری آپ الگورتھم نوں «کافی الجھیا ہویا» آکھدے نیں۔ مقالہ نظریاتی اے: ایہہ کسے عمل درآمد یا بینچ مارک دی رپورٹ نئیں دیندا۔