بعد 40 عامًا، يسقط حدّ السرعة في البحث عن العُصَب
تخيّل شبكة اجتماعية تضم n شخصًا. هل توجد مجموعة من k منهم يعرف بعضهم بعضًا جميعًا؟ يسمّي علماء الحاسوب مثل هذه المجموعة عُصبة k (k-clique)، وإيجادها مسألة كلاسيكية ذات تطبيقات لا تُحصى. والنهج الساذج يفحص كل مجموعة ممكنة من k شخصًا، وعددها نحو n^k — وهو أمر ميؤوس منه في الشبكات الكبيرة.
حيلة من 1985 وتحدٍّ طويل
قبل أكثر من 40 عامًا، وجد ياروسلاف نيشيتريل (Jaroslav Nešetřil) وسفاتوبلوك بولياك (Svatopluk Poljak) طريقًا مختصرًا. فقد حوّلا البحث عن عُصبة k إلى البحث عن مثلث في مخطط (graph) أكبر، وهذا بدوره يمكن إنجازه عبر ضرب المصفوفات، وهي جداول كبيرة من الأعداد. وتعتمد الكلفة على ω، أُسّ ضرب المصفوفات: إذ تستغرق طريقتهما نحو n^(ωk/3) خطوة. ولا أحد يعرف ω بدقة. فهي لا تقل عن 2، ويستشهد المقال بحدّ أعلى حديث قدره 9/4.
لم يُتفوَّق قط على أُسّ طريقة 1985 هذه. ففي عام 2004، تحدّى غيرهارد فوغينغر (Gerhard Woeginger) الباحثين أن يحققوا ما هو أفضل لقيمة ثابتة ما من k؛ ومرّ أكثر من عقدين. وفي الأثناء، صارت فرضية عُصبة k (k-Clique Hypothesis) — ومفادها أن n^(ωk/3) هو في جوهره أفضل ما يمكن — أساسًا لـ«التعقيد الدقيق الحبيبات» (fine-grained complexity). واستخدمها الباحثون للمحاججة بأن مسائل أخرى كثيرة، من تحليل القواعد النحوية (parsing grammars) إلى تحليل البيانات المضغوطة، لا يمكن حلها أسرع هي الأخرى.
هدف متحرك
كان لدحض هذه الفرضية صعوبة خاصة. فالكلفة التي تتنبأ بها تعتمد على ω، وهي مجهولة. وخوارزميةٌ تتفوق على أفضل قيمة حالية لـω قد تكفّ عن التفوق على الفرضية إذا وجد أحدهم لاحقًا طريقة أسرع لضرب المصفوفات.
أما فيرجينيا فاسيليفسكا ويليامز (Virginia Vassilevska Williams)، من معهد ماساتشوستس للتكنولوجيا (MIT)، وأور زامير (Or Zamir)، من جامعة تل أبيب، فيلتفّان على المشكلة. إذ يبرهنان أنه لكل k كبيرة بما يكفي، يمكن إيجاد عُصبة k — بل وعدّها أيضًا — في نحو n^((ω/3 − c)k) خطوة، حيث c ثابت موجب لا يعتمد على k ولا على ω. ويُقاس هذا التوفير بالنسبة إلى القيمة الحقيقية لـω، أيًّا كانت. ويصمد حتى لو كانت ω = 2، وهي أفضل حالة يمكن تصوّرها.
طيّ إسفين
يتعلق جوهر الطريقة بأنماط من تسعة رؤوس (vertices). فالنهج المعياري يقسمها إلى ثلاث مجموعات من ثلاثة ويضرب ثلاث مصفوفات ضخمة. أما المؤلفان فينظران إلى إسفين (wedge) — ضلعين يشتركان في رأس — ويُدرجان، بين اثنتين من المصفوفات، جدولًا لا يغيّر شيئًا: مصفوفة الوحدة (identity). ثم يكتبان مصفوفة الوحدة هذه على شكل مجموع لبضع «مبادلات» (swaps)، تدمج كلٌّ منها ضلعَي الإسفين في ضلع واحد، إضافةً إلى باقٍ ذي رتبة منخفضة.
تعطي المبادلات أنماطًا أبسط بأضلاع أقل، تُعالَج بالطريقة نفسها مرة أخرى؛ ونمط من تسعة رؤوس لا يملك أكثر من 36 ضلعًا، لذا ينتهي الاستدعاء الذاتي (recursion). ويقلّص الباقي ذو الرتبة المنخفضة المصفوفاتِ المطلوب ضربها. وتطبيق الحيلة على إسفينين منفصلين في آن واحد هو ما يحفظ المكسب حتى حين تكون ω = 2. ومن ثَمّ يمكن تجميع أي k من مضاعفات التسعة في تسع كتل.
حقيقي لكنه ضئيل
لا يقدّم المؤلفان أرقامًا للمكسب. ويصفان الثوابت بأنها تتراوح «بين متناهية الصغر من دون تحسين، وضئيلة مع تحسينات كبيرة». فالمقصود ليس السرعة في الممارسة: بل أن حاجزًا ظُنّ صحيحًا لعقود لا وجود له.
وتتجاوز العواقب العُصَب. فالخوارزميات الدقيقة لمسائل التحسين الصعبة مثل Max-Cut وMax-2-SAT، التي كانت تستغرق نحو 2^(ωn/3) خطوة لـn متغيرًا، تحصل الآن هي أيضًا على أُسّ أصغر. وكذلك عدّ نسخ أي مخطط صغير ثابت.
ما فعله الذكاء الاصطناعي
في قسم مخصص، يصف المؤلفان كيف عملا مع ChatGPT-6، مستخدمَين إياه عبر واجهته العامة على الويب. فانطلاقًا من أفكارهما الخاصة بالعُصَب المؤلفة من خمسة أشخاص، ومن نتيجة حديثة لـOpenAI تدحض حدسية أخرى، هي فرضية الزمن الأسّي (Exponential Time Hypothesis)، وجد النموذج تحسينًا أوليًا معقدًا لعُصَب الخمسة (5-cliques). ثم استخلص منه المؤلفان، بمساعدة الذكاء الاصطناعي، التفكيك الجبري الذي يقع في صميم البرهان، والذي يعدّانه «مساهمة الذكاء الاصطناعي بشكل شبه خالص». أما الإطار الخوارزمي المبني حوله فهو، بحسب قولهما، من صنعهما في المقام الأول.
وتبرز ملاحظة واحدة. فالبراهين الغامضة التي يولّدها الذكاء الاصطناعي صعبة القراءة على البشر، كما يلاحظ المؤلفان — وقد «أدهشهما أنها صعبة الفهم أيضًا على الذكاء الاصطناعي نفسه».
