سقوط حاجز يعود إلى عام 1962 في علوم الحاسوب

الدورة الهاميلتونية رحلة ذهاب وإياب عبر شبكة تزور كل نقطة مرة واحدة بالضبط ثم تعود إلى نقطة البداية. وفي الشبكة الموجَّهة، كل وصلة سهمٌ لا يمكن سلوكه إلا في اتجاه واحد، كالشارع ذي الاتجاه الواحد. والصيغة الموزونة لهذه المسألة هي مسألة البائع المتجوّل غير المتناظرة.

وتحديد ما إذا كانت مثل هذه الدورة موجودة مسألة صعبة نموذجية في الكتب الدراسية. ففي عام 1962، قدّم ريتشارد بيلمان، ومستقلًا عنه مايكل هيلد وريتشارد كارب، خوارزميات برمجة ديناميكية تحلّها في زمن يقارب 2ⁿ لشبكة من n نقطة (بإهمال العوامل التي لا تنمو إلا نموًا متعدد الحدود). ولأكثر من ستين عامًا، لم يتمكن أحد من القيام بما هو أفضل جوهريًا على الشبكات الموجَّهة العامة.

ابن العمّ غير الموجَّه كان قد سقط بالفعل

بالنسبة إلى الشبكات ذات الوصلات ثنائية الاتجاه، كسر أندرياس بيوركلوند الحاجز عام 2014 بخوارزمية عشوائية تعمل في 1.657ⁿ، وهو عمل نال عنه جائزة نيرود EATCS–IPEC لعام 2016، وفقًا للورقة. ولا تزال الأسرع المعروفة للشبكات غير الموجَّهة العامة. أما الموجَّهة، فلم يتحقق فيها تقدّم إلا في حالات خاصة، كالشبكات ثنائية التجزئة والشبكات ذات الوصلات القليلة لكل نقطة، أو في ظل فرضية غير مبرهنة هي حدسية شتراسن حول الرتبة المقاربة.

الحدّ الجديد

يقدّم الآن توموهيرو كوانا من جامعة طوكيو وسوه كومابي من شركة CyberAgent في طوكيو خوارزمية عشوائية تحسم المسألة الموجَّهة في زمن

O((375/196)ⁿ) = O(1.9133ⁿ)**.

وبالنسبة إلى الشبكات الموجَّهة العامة، فهذا أول تحسين في أساس الدالة الأسية منذ عام 1962.

العدّ بالفردي والزوجي

الصعوبة دقيقة. فعدّ الدورات بترديد 2، أي معرفة ما إذا كان عددها فرديًا أم زوجيًا فقط، كان ممكنًا بالفعل في زمن دون 2ⁿ. لكن عددًا زوجيًا غير صفري من الدورات يبدو تمامًا مثل الصفر. والحل الكلاسيكي هو إعطاء الوصلات أوزانًا عشوائية بحيث يصبح الحلّ وحيدًا عند وزن إجمالي ما (وهذه هي مأخوذة العزل)؛ لكن الطريقة السريعة لعدّ الزوجية لم تكن قادرة على التعامل مع الأوزان.

وصفة المؤلفَين، بكلمات بسيطة:

1. خمّن سهمًا واحدًا من الدورة، وابحث بدلًا من ذلك عن مسار يمرّ بكل النقاط من أحد طرفي ذلك السهم إلى الطرف الآخر.
2. احذف كل سهم عشوائيًا باحتمال 1/50.
3. عند كل نقطة، أنشئ ثلاث مجموعات من الأسهم الداخلة، وانسخ كل سهم باقٍ إلى مجموعة عشوائية غير فارغة من المجموعات.
4. إذا كانت هناك جولة، فإنه باحتمال لا يقل عن (49/50)ⁿ⁻¹ يمكن اختيار مجموعة واحدة لكل نقطة بحيث يكون عدد المسارات الصالحة فرديًا.
5. أعطِ كل مجموعة، لا كل سهم، وزنًا عشوائيًا. الآن تنجح حيلة العزل، ويكفي نحو (50/49)ⁿ تكرارًا.
6. يحسب كل تكرار أعداد الفردية والزوجية عند كل وزن إجمالي في زمن (15/8)ⁿ، باستخدام مجاميع محدِّدات المصفوفات التي تعود إلى بيوركلوند وكاسكي وكوتيس، و“تخطيط خطي” (linearisation) عشوائي استخدمه أيضًا أرفيند وغوروسوامي.

اضرب الاثنين: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ.

برهان ولّدته آلة

تنتهي الورقة بإقرار بشأن الذكاء الاصطناعي التوليدي: ولّد ChatGPT 6 Astra برهان المبرهنة الرئيسية وساعد في صياغة المخطوطة. وقدّم المؤلفان صيغ القضايا الوسيطة، التي تعطي قراءة توافقية للحل الأصلي الذي قدّمه النموذج، ثم تحققا من كل شيء ونقّحاه، ويتحمّلان المسؤولية الكاملة.

والنتيجة نظرية، إذ لم يُشغَّل أي برنامج، والخوارزمية عشوائية، مع احتمال ضئيل للخطأ في كلا الاتجاهين. وبين 1.9133 للشوارع ذات الاتجاه الواحد و1.657 للشوارع ذات الاتجاهين، لا تزال هناك فجوة واسعة مفتوحة.