فرزٌ بمقارنات ممنوعة، وبسرعة تكاد تماثل المعتاد
لترتيب n عنصرًا بمقارنتها اثنين اثنين، تكون نحو n log n مقارنة ضرورية وكافية في آن واحد. لكن ذلك يفترض أن أي عنصرين يمكن مقارنتهما.
وكثيرًا ما يتعذّر ذلك. يستعير المؤلفون مثالًا من بحث صدر عام 2011: يتقدم عدة مرشحين للوظيفة نفسها، ولكلٍّ منهم مزكّون. ولا يمكن مقارنة مرشحَين إلا إذا كان أحد المزكّين يعرفهما كليهما. وتشكّل المقارنات المسموح بها شبكة، أي بيانًا (graph): كل عنصر نقطة، وكل مقارنة مسموح بها وصلة. والترتيب الحقيقي خفي، لكن من المضمون أن البيان يحتويه، في صورة مسار يصل كل عنصر بالذي يليه. والسؤال: كم مقارنة يتطلب استرداد الترتيب؟ هذا هو الفرز المعمَّم (generalized sorting).
لماذا تفشل الحيل المعتادة
تعتمد الخوارزميات الكلاسيكية على حرية الاختيار. فخوارزمية QuickSort تختار «محورًا» (pivot) وتقارنه بمعظم العناصر الأخرى، لكن بيانًا اعتباطيًا قد لا يحتوي على أي عنصر متصل بمعظم العناصر الأخرى. وخوارزمية MergeSort تقسم العناصر إلى مجموعات وتفرز كلًا منها، لكن مجموعةً ما قد لا تكون قابلة للفرز وحدها: فعنصران متجاوران في الترتيب النهائي ليسا بالضرورة متصلين داخلها. وعلى نحو أعمق، يتوفر في الفرز العادي دائمًا مقارنةٌ تستبعد حصة كبيرة من الترتيبات الممكنة؛ أما مع المقارنات المقيَّدة، فقد لا توجد أي مقارنة من هذا النوع.
كان التقدم بطيئًا. ففي 2011، وجد زيي هوانغ (Zhiyi Huang) وسامباث كانان (Sampath Kannan) وسانجيف خانا (Sanjeev Khanna) طريقة تستخدم نحو n¹·⁵ مقارنة، بإهمال العوامل اللوغاريتمية، وظل هذا الحد صامدًا للبيانات الاعتباطية منذ ذلك الحين. بل تساءلوا هل يمكن أن تكون المسألة أصعب جوهريًا من الفرز العادي، فتحتاج إلى n مرفوعًا إلى قوة أكبر من 1.
التنبؤ أولًا، والإصلاح لاحقًا
ويجيب الآن عن هذا السؤال سانجيف خانا، من جامعة نيويورك (New York University)، وآرون بوترمان (Aaron Putterman)، من جامعة هارفارد (Harvard University)، وجونكاي سونغ (Junkai Song)، من جامعة نيويورك أيضًا: لا. فخوارزميتهم العشوائية (randomised) تفرز بنحو n log⁴ n مقارنة في المتوسط، على أي بيان — أي أكثر من الفرز العادي ببضعة عوامل لوغاريتمية فقط. وهي، كما يكتبون، «بسيطة نسبيًا». لكن المكسب نظري: فثوابت البرهان هائلة (عوامل مثل 2³²)، لذا لا تظهر الأفضلية إلا عند قيم كبيرة جدًا لـn.
وهي تبني على نتيجة معروفة: إذا أعطاك أحدهم تخمينًا لاتجاه كل وصلة، أخطأ في w منها، أمكن استرداد الترتيب بنحو n log n + w مقارنة. فتصبح المهمة إنتاج تخمين قليل الأخطاء بقليل من المقارنات. والخطوات الأساسية:
- تخمين أولي تقريبي. قارن عيّنة عشوائية من الأزواج المتصلة واختر أي ترتيب يتسق مع الإجابات. يرتكب هذا التخمين أخطاء كثيرة، لكن ليست كثيرة جدًا.
- عزل الأخطاء بدل إصلاحها. فبدل تصحيح التخمينات الخاطئة، تعثر الخوارزمية على أجزاء من البيان تكون فيها الأخطاء أكثف من المتوسط وتضعها جانبًا. وكل جولة تقلّص الأخطاء المتبقية، في المتوسط، إلى الربع.
- العودة لاحقًا. تُعالَج الوصلات الموضوعة جانبًا في مرحلة لاحقة. وكل مرحلة تحسم نصف الوصلات التي لا تزال معلّقة على الأقل، فتكفي نحو عشرين مرحلة لمليون وصلة.
برهان عُثر عليه بمساعدة الآلات
إفصاح البحث عن استخدام الذكاء الاصطناعي مفصّل على نحو غير مألوف. فهو ينص على أن ChatGPT 6-Astra «كان أساسيًا في إثبات الحدود المحسَّنة». فقد وجد نموذج أولًا خوارزمية تستخدم نحو n¹·³³ مقارنة، ثم توقف عن التقدم. فحسّنها المؤلفون إلى n¹·²؛ ثم، بعد عشرات المطالبات (prompts) على مدى عدة أسابيع، وجدت النماذج تحسينات متتالية — n^(10/9) وn^(17/16) وn^(19/18) — قبل الوصول إلى الخوارزمية شبه الخطية. ويضيف المؤلفون أنه ليس واضحًا إن كانت خطوتهم الوسيطة أساسية لذلك الاكتشاف النهائي.
ما الذي لا يزال مفتوحًا
تعدّ النتيجة المقارناتِ لا زمن الحساب: فالخوارزمية، بصيغتها الحالية، لا تعمل في زمن متعدد الحدود (polynomial time)، في حين كانت طريقة 2011 كذلك. ويسرد المؤلفون ثلاثة أسئلة مفتوحة: هل يمكن التخلص من العوامل اللوغاريتمية المتبقية، وهل يمكن لخوارزمية خالية من العشوائية أن تبلغ الأداء نفسه، وهل يمكن لخوارزمية فعالة أن تصل إلى العدد نفسه من المقارنات — أو حتى أن تتفوق على n¹·⁵ أصلًا.
