اختيار أعداد مجموعها هدفٌ محدد، بسرعة تكاد تضاهي قراءتها

إليك لغزًا يستطيع أي أحد صياغته. لديك قائمة من الأعداد الصحيحة — لنقل 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. وهي حتمية، وتقبل الأعداد السالبة والقيم المكررة، ومرفقة ببرهان رياضي. ويصف المؤلفون هذا الزمن بأنه شبه أمثل.

وتمتد النتيجة إلى المتجهات: اختيار عناصر بحيث تبلغ عدة مجاميع أهدافها في آنٍ واحد، بزمن N^(d+ε) لـd من الإحداثيات. وهذا بدوره يجيب عن جزء من سؤال طرحته عدة مجموعات حول البرمجة بالأعداد الصحيحة — أي إيجاد حلول بأعداد صحيحة لأنظمة معادلات متغيراتها محدودة. وتُستخلص نتيجتان صراحةً: تقسيم مجموعة من الأعداد إلى نصفين متساويين، وتوزيع المهام بين آلتين متطابقتين بأكبر قدر ممكن من التوازن.

رفع الأعداد إلى بُعد أعلى

الفكرة الأساسية هندسية. فقد كان معروفًا أن المسألة سهلة حين تكون الأعداد كثيفة ويقع الهدف في عمق نطاق المجاميع الممكنة. وملاحظة المؤلفين: يمكن لمجموعة متناثرة من الأعداد أن تبدو كثيفة حين يُنظر إليها في بُعد أعلى.

ومثالهم المجموعة {11, 12, 22, 24}. اكتب 11 و22 على أنهما خطوة وخطوتان على محور أول، و12 و24 على أنهما خطوة وخطوتان على محور ثانٍ. عندئذ تملأ المجاميع الممكنة كل نقطة من مربع صغير أبعاده 4 في 4. لكن اضغط هذا المربع من جديد على خط مستقيم — بحساب 11x + 12y — فتشكّل المجاميع سبعة عناقيد منفصلة تفصل بينها فجوات، متناثرة بين 0 و69. والفجوات وهمٌ يصنعه الإسقاط؛ ففي بعدين تكون البنية بسيطة.

تبني الخوارزمية مثل هذه الإحداثيات عالية الأبعاد لأي مُدخل، مستعينةً بنتائج من التوافقيات الجمعية (additive combinatorics). وداخل المنطقة «الممتلئة»، تأتي الإجابات بلا كلفة. ولا تحتاج إلى عمل حقيقي إلا منطقة رقيقة قرب الحافة، تقسّمها الخوارزمية إلى مسائل أصغر وتحلّها بالاستدعاء الذاتي. وكل جولة تقلّص هذه المنطقة تقليصًا حادًا، ولا يُضاف في المجمل إلا عدد ثابت من الأبعاد الجديدة.

كيف بُني البرهان

تبدأ الورقة بـ«إخلاء مسؤولية بشأن الذكاء الاصطناعي». فقد صمّم المؤلفون بأنفسهم المسار الرئيسي للبرهان، بناءً على أعمالهم الحديثة حول الصيغ الكثيفة متعددة الأبعاد للمسألة. ثم استخدموا نموذج ذكاء اصطناعي، هو GPT Astra Ultra، لتحويل هذه الأفكار إلى براهين رياضية كاملة. وقد تعثّر في عدة مُبرهنات مساعدة (lemmas)، حُلّت بأفكار من المؤلفين؛ وتوثّق مذكرة بحثية منشورة هذه المحادثات. وبعد إنجاز الخوارزمية العشوائية الأساسية، وسّعها النموذج إلى الصيغ الحتمية ومتعددة الأبعاد «دون أي توجيه من المؤلفين». كما صاغ النموذج مسودة الورقة، وتحقّق — كما يكتب المؤلفون — من نتائجها الرئيسية ببرهان في مساعد البراهين Lean 4. ويتحمّل المؤلفون المسؤولية الكاملة عن المحتوى.

ليس خط النهاية تمامًا

الأُسّ هو 1 + ε لا 1 بالضبط، والثوابت الخفية تكبر كلما صغر ε؛ ولم يُحسَّن الاعتماد على عدد الأبعاد. ويصف المؤلفون أنفسهم الخوارزمية بأنها «معقّدة إلى حد بعيد». والورقة نظرية: لا تعرض أي تطبيق برمجي ولا اختبارات أداء.