سامي الطياح
إنه يوم الفطائر، لذلك دعونا نتخيل كومةً من الفطائر؛ إن لم تكن جيدًا في صنعها فمن المحتمل أن تأتي الفطائر بأحجام مختلفة، ما يجعل كومةً منها تبدو غير مرتبةٍ للغاية؛ توجد طريقة واحدة لجعلها تبدو أفضل، وهي ترتيبها حسب الحجم بحيث يكون لديك الأكبر في الأسفل، والأصغر في الأعلى.
كيف يمكنك ترتيب الفطائر بهذه الطريقة إذا كانت الأداة الوحيدة التي تمتلكها هي الملعقة التي يمكنك استخدامها لقلب الفطائر؟ هنالك طريقة واحدة، وهي كالآتي: أولًا: رَقِّم الفطائر حسب الحجم 1 للأصغر 2 للأكبر من 1، وهكذا. ثم ابحث عن أوّل فطيرةٍ (عدّ من أعلى المجموعة) موجودةٍ في المكان الخطأ (أي يوجد فطائرُ أصغر تحتها)، على سبيل المثال، قد تجد أن رقم الفطيرة 3 في الموضع 2.
الآن أدخل الملعقة أسفل الفطيرة المخالفة (الموجودة في المكان الخطأ) واقلب الكومة بأكملها أعلى الملعقة، الفطيرة المخالفة الآن هي في القمة. بعد ذلك، أدخل الملعقة أسفل الموضع الذي من المفترض أن تكون فيه الفطيرة المخالفة (الموضع 3 في مثالنا)، ثم اقلب المجموعة التي أعلى الملعقة مرة أخرى، الفطيرة المخالفة الآن في الوضع الذي من المفترض أن تكون فيه.
إذا واصلت العمل على هذا المنوال مع كل فطيرة مخالفة، فسوف ينتهي بك الأمر في نهاية المطاف بمجموعةٍ مرتبة حسب الحجم، واتضح بذلك أنه إذا كان لديك عدد 
من الفطائر في المجموع الكلي، فتحتاج هذه الطريقة 
قلبة كحدٍّ أقصى.
من الجيد معرفة ذلك، لكن لا يزال يعني أنك قد تحتاج إلى الكثير من التقليب. بالنسبة لمجموعة من الفطائر عددها 
، قد يأخذ منك الأمر 
قلبةً، وهو أمر مملٌّ. هل هناك طريقة أفضل، وإذا كانت الإجابة بنعم، فكم عدد القلبات التي تتطلبها؟
هذا سؤال صعب للغاية. أثبت بيل جيتس Bill Gates، جنبًا إلى جنب مع كريستوس باباديميتريو Christos Papadimitriou، أول تحسين كبير على الحد 
، عندما كان جيتس طالبًا في جامعة هارفارد في منتصف السبعينيات، أثبت الاثنان أن كلّ كومةٍ من الفطائر يمكن فرزها من خلال 
قلبة على الأكثر. لم يتحسّن هذا الحد حتى عام 2009، حين أظهر فريق مكون من سبعة باحثين من جامعة تكساس في دالاس، أنه يمكن فرز كل مجموعة بمقدار 
قلبة على الأكثر، وذلك عندما قسموا المشكلة إلى 2220 حالة مختلفة.
في عام 2011، أظهر فريقٌ آخر من الباحثين أن مشكلة العثور على أقصر تسلسلٍ من التقلبات لمجموعةٍ معينة من الفطائر هو ما يُسمى NP-hard. إذا تحدثنا بشكل فضفاض فهذا يعني على حد علم الجميع أن المشكلة صعبةٌ للغاية حقًا.
لا تتعلق مشكلة تقليب الفطائر فقط بالفطائر، ولكن يوجد هنالك تطبيقات في جميع أنواع السياقات حيث تحتاج فيها الأشياء إلى الفرز، على سبيل المثال تقليب الكروموسوم وتطوره.
- ترجمة: سامي طياح.
- مراجعة: رأفت فياض.
