برگزیدن عددهایی که جمعشان جور درمی‌آید، تقریباً به سرعت خواندنشان
این معمایی است که هر کسی می‌تواند بیانش کند. فهرستی از عددهای صحیح دارید — مثلاً ۳، ۹، ۱۴، ۲۰ — و یک هدف، مثلاً ۲۳. آیا می‌توانید برخی را طوری برگزینید که جمعشان دقیقاً برابر هدف شود؟ (این‌جا، بله: ۳ + ۲۰ یا ۹ + ۱۴.) این جمع زیرمجموعه (Subset Sum) است، یکی از بنیادی‌ترین مسائل علوم رایانه. مقاله آن را مسئله‌ای بنیادی و NP-کامل توصیف می‌کند، خانواده‌ای از مسائل که به دشواریِ حل دقیق شناخته می‌شوند.
اما یک راه گریز هست. اگر عددها خیلی بزرگ نباشند، الگوریتم‌های زیرکانه در زمانی اجرا می‌شوند که به اندازهٔ آن‌ها بستگی دارد. روش کلاسیک بلمن در ۱۹۵۷ زمانی متناسب با شمار عددها، n، ضرب در هدف، t، می‌گیرد. از آن پس الگوریتم‌ها پیوسته بهتر شده‌اند:
- پیسینگر (۱۹۹۹): متناسب با n × N، که N بزرگ‌ترین عدد است؛
- برینگمن (۲۰۱۷): تقریباً n + t؛
- چند گروه (۲۰۲۱ تا ۲۰۲۴): تقریباً n + N^(5/3)، سپس n + N^(3/2).
جام مقدس زمانی تقریباً برابر n + N بود — نه چندان بیش از خواندن ورودی. پژوهشگران این حوزه آن را «حیاتی‌ترین مسئلهٔ گشودهٔ» این خط پژوهشی خوانده بودند.
به یک مویی هدف
لین چن، یوچن مائو و گوچوان ژانگ از دانشگاه ژجیانگ در چین، الگوریتمی ارائه می‌دهند که در زمان n + N^(1+ε) اجرا می‌شود، که در آن ε می‌تواند هر عدد مثبت کوچکی باشد که از پیش تعیین شده — ۰٫۱، ۰٫۰۱، ۰٫۰۰۱. الگوریتم قطعی (deterministic) است، عددهای منفی و مقادیر تکراری را می‌پذیرد، و با اثباتی ریاضی همراه است. نویسندگان این زمان را تقریباً بهینه می‌نامند.
نتیجه به بردارها هم گسترش می‌یابد: برگزیدن اقلام طوری که چند جمع هم‌زمان به هدفشان برسند، با زمان N^(d+ε) برای d مؤلفه. این نیز به بخشی از پرسشی پاسخ می‌دهد که چند گروه دربارهٔ برنامه‌ریزی عدد صحیح (integer programming) مطرح کرده بودند — یافتن جواب‌های عدد صحیح برای دستگاه‌هایی از معادلات که متغیرهایشان کران‌دارند. دو پیامد به‌صراحت بررسی شده‌اند: تقسیم مجموعه‌ای از عددها به دو نیمهٔ برابر، و تقسیم کارها میان دو ماشین یکسان تا حد ممکن به‌طور مساوی.
بردن عددها به بُعدی بالاتر
ایدهٔ کلیدی هندسی است. پیش‌تر معلوم بود که وقتی عددها چگال باشند و هدف به‌خوبی درون گسترهٔ جمع‌های ممکن قرار گیرد، مسئله آسان است. مشاهدهٔ نویسندگان: مجموعه‌ای تُنُک از عددها، وقتی در بُعدی بالاتر دیده شود، می‌تواند چگال به نظر برسد.
مثال آن‌ها مجموعهٔ {11, 12, 22, 24} است. ۱۱ و ۲۲ را یک گام و دو گام در امتداد محور نخست بنویسید، و ۱۲ و ۲۴ را یک گام و دو گام در امتداد محور دوم. آن‌گاه جمع‌های ممکن همهٔ نقاط یک مربع کوچک ۴ در ۴ را پر می‌کنند. اما این مربع را دوباره روی یک خط فشرده کنید — با محاسبهٔ 11x + 12y — و جمع‌ها هفت خوشهٔ جدا با شکاف‌هایی میانشان می‌سازند که میان ۰ و ۶۹ پراکنده‌اند. شکاف‌ها توهمی از تصویرکردن (projection)اند؛ در دو بُعد، ساختار ساده است.
الگوریتم برای هر ورودی چنین مختصات بالابُعدی‌ای می‌سازد و از نتایج ترکیبیات جمعی (additive combinatorics) بهره می‌گیرد. درون ناحیهٔ «پرشده»، پاسخ‌ها رایگان به دست می‌آیند. فقط نوار باریکی نزدیک لبه به کار واقعی نیاز دارد که الگوریتم آن را به مسائل کوچک‌تر می‌شکند و به‌طور بازگشتی حل می‌کند. هر دور این نوار را به‌شدت باریک‌تر می‌کند و فقط شمار ثابتی بُعد تازه افزوده می‌شود.
اثبات چگونه ساخته شد
مقاله با یک «سلب مسئولیت هوش مصنوعی» آغاز می‌شود. نویسندگان مسیر اصلی اثبات را خودشان طراحی کردند، بر پایهٔ کار اخیر خودشان دربارهٔ نسخه‌های چگال و چندبُعدی مسئله. سپس از یک مدل هوش مصنوعی، GPT Astra Ultra، استفاده کردند تا این ایده‌ها را به اثبات‌های ریاضی کامل بدل کند. مدل در چند لم گیر کرد که با ایده‌های نویسندگان حل شدند؛ یک یادداشت پژوهشی عمومی گفت‌وگوها را ثبت کرده است. پس از تکمیل الگوریتم تصادفی پایه، مدل آن را «بی هیچ راهنمایی از سوی نویسندگان» به نسخه‌های قطعی و چندبُعدی گسترش داد. مدل پیش‌نویس مقاله را هم نوشت و، به نوشتهٔ نویسندگان، نتایج اصلی‌اش را با اثباتی در دستیار اثبات Lean 4 راستی‌آزمایی کرد. نویسندگان مسئولیت کامل محتوا را بر عهده می‌گیرند.
هنوز خط پایان نیست
نما (exponent) به‌جای دقیقاً ۱، برابر ۱ + ε است، و ثابت‌های پنهان با کوچک شدن ε بزرگ می‌شوند؛ وابستگی به شمار بُعدها بهینه نشده است. خود نویسندگان الگوریتم را «بسیار پیچیده» توصیف می‌کنند. مقاله نظری است: هیچ پیاده‌سازی یا محک‌زنی‌ای گزارش نمی‌کند.