ما هي أفضل طريقة لحل المشاكل الصعبة؟ هذا هو السؤال الذي يقع في قلب مجال فرعي من علوم الكمبيوتر يسمى نظرية التعقيد الحسابي. من الصعب الإجابة على هذا السؤال، ولكن قلبه ليصبح أسهل. النهج الأسوأ هو دائمًا التجربة والخطأ، والذي يتضمن إدخال الحلول الممكنة حتى ينجح أحد الحلول. لكن بالنسبة لبعض المشكلات، يبدو ببساطة أنه لا توجد بدائل - فالأسلوب الأسوأ هو أيضًا الأفضل.

وقال الباحثون إن الباحثين تساءلوا منذ فترة طويلة عما إذا كان هذا هو الحال بالفعل راهول إيلانجو، طالب دراسات عليا يدرس نظرية التعقيد في معهد ماساتشوستس للتكنولوجيا. "يمكنك أن تسأل: هل هناك مشكلات يعتبر التخمين والتحقق هو الحل الأمثل لها؟"

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

ولكن في نوفمبر الماضي، مجموعتان من الباحثين بشكل مستقل اكتشف خوارزمية أخرى لمشكلات الضغط، وهي أسرع قليلاً من التحقق من جميع الإجابات المحتملة. يعمل النهج الجديد من خلال تكييف خوارزمية اخترعها علماء التشفير قبل 25 عامًا لمهاجمة مشكلة مختلفة. هناك قيد واحد فقط: تحتاج إلى تخصيص الخوارزمية لتناسب حجم مجموعة البيانات الخاصة بك.

قال: "إنها نتائج جميلة ومهمة حقًا". اريك الندر، عالم الكمبيوتر النظري في جامعة روتجرز.

تعريف الصلابة

النتائج الجديدة هي الأحدث في التحقيق في مسألة تمت دراستها لأول مرة في الاتحاد السوفييتي، قبل وقت طويل من ظهور نظرية التعقيد. وقال أليندر: "قبل أن أكون في المدرسة الابتدائية، كان الناس في روسيا يصوغون هذا الأمر".

إن المشكلة الحسابية المحددة التي درسها هؤلاء الباحثون السوفييت، والتي تسمى مشكلة الحد الأدنى لحجم الدائرة، تشبه تلك التي يواجهها مصممو أجهزة الكمبيوتر طوال الوقت. إذا تم إعطاؤك مواصفات كاملة لكيفية عمل الدائرة الإلكترونية، فهل يمكنك العثور على أبسط دائرة يمكنها القيام بهذه المهمة؟ ولم يكن أحد يعرف كيفية حل هذه المشكلة دون استخدام كلمة "perebor" - وهي كلمة روسية تعادل تقريبًا "البحث الشامل".

تعد مشكلة الحد الأدنى لحجم الدائرة مثالاً على مشكلة الضغط. يمكنك وصف سلوك الدائرة باستخدام سلسلة طويلة من البتات - 0 و1 - ثم التساؤل عما إذا كانت هناك طريقة لإعادة إنتاج نفس السلوك باستخدام عدد أقل من البتات. قد يستغرق فحص جميع تخطيطات الدوائر الممكنة وقتًا ينمو بشكل كبير مع عدد البتات في السلسلة.

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

في عام 1959، ادعى باحث بارز يدعى سيرجي يابلونسكي أنه أثبت أن البحث الشامل كان في الحقيقة الطريقة الوحيدة لحل مشكلة الحد الأدنى لحجم الدائرة. لكن برهانه ترك بعض الثغرات. لاحظ بعض الباحثين العيوب في ذلك الوقت، لكن يابلونسكي كان مؤثرًا بدرجة كافية لتثبيط معظم الباحثين الآخرين عن العمل على السؤال السابق.

في العقود التي تلت ذلك، قام عدد قليل من الباحثين بدراسة مشاكل الضغط، وكان السؤال التقريبي معروفًا في الغالب كحاشية في نظرية التعقيد في عصور ما قبل التاريخ. لم يحظ هذا السؤال باهتمام واسع النطاق إلا مؤخرًا، بعد أن اكتشف الباحثون رابطًا غريبًا بين مشكلات الضغط وأسس التشفير.

حركة المرور في اتجاه واحد

يستخدم التشفير الحديث مشاكل حسابية صعبة لحماية الرسائل السرية. لكن الصلابة الحسابية تكون مفيدة فقط إذا كانت غير متماثلة، أي إذا كان من الصعب فك تشفير الرسائل المشفرة ولكن ليس من الصعب تشفير الرسائل في المقام الأول.

في كل مخطط تشفير، أصل عدم التماثل هذا هو كائن رياضي يسمى دالة أحادية الاتجاه، والتي تحول سلاسل البت المدخلة إلى سلاسل مخرجات بنفس الطول. عند وجود مدخلات لدالة أحادية الاتجاه، من السهل حساب المخرجات، ولكن في حالة وجود مخرجات يكون من الصعب عكس الدالة - أي إجراء هندسة عكسية لها واسترداد المدخلات.

قال أليندر: "إن مصممي التشفير يرغبون حقًا في الحصول على وظائف أحادية الاتجاه وقابلة للحساب بكفاءة عالية، والتي يصعب حقًا عكسها". يبدو أن العديد من الدوال الرياضية تمتلك هذه الخاصية، وصعوبة عكس هذه الدوال تنبع من الصعوبة الواضحة في حل المسائل الحسابية المختلفة.

لسوء الحظ، لا يعرف علماء التشفير على وجه اليقين ما إذا كان من الصعب حقًا عكس أي من هذه الوظائف - في الواقع، من الممكن عدم وجود وظائف حقيقية أحادية الاتجاه. ويستمر عدم اليقين هذا بسبب وجود منظري التعقيد ناضل لمدة 50 عاما لإثبات أن المشاكل التي تبدو صعبة هي في الواقع صعبة. إذا لم يكن الأمر كذلك، وإذا اكتشف الباحثون خوارزميات فائقة السرعة لهذه المشكلات، فسيكون ذلك كارثيًا بالنسبة للتشفير، على غرار توجيه السيارات المسرعة فجأة في كلا الاتجاهين في شارع ذو اتجاه واحد.

على الرغم من أن الفهم الشامل للصلابة الحسابية لا يزال بعيد المنال، فقد حقق علماء التشفير مؤخرًا تقدمًا مثيرًا نحو نظرية موحدة للوظائف ذات الاتجاه الواحد. تم اتخاذ خطوة كبيرة في عام 2020، عندما قام عالم التشفير في جامعة تل أبيب رافائيل باس وطالبه المتخرج ياني ليو أثبت أن الوظائف ذات الاتجاه الواحد هي متصلة بشكل وثيق لمشكلة ضغط محددة تسمى مشكلة تعقيد كولموجوروف المحددة بالزمن.

إذا كان من الصعب حقًا حل هذه المشكلة بالنسبة لمعظم المدخلات، فإن نتيجة باس وليو تعطي وصفة لكيفية إنشاء دالة أحادية الاتجاه يمكن إثبات صعوبتها - وهي دالة مضمونة الأمان حتى لو تبين أن المشكلات الحسابية الأخرى أسهل بكثير مما توقعه الباحثون. ولكن إذا كانت هناك خوارزمية سريعة لحل مشكلة تعقيد كولموجوروف المحددة زمنياً، فإن التشفير محكوم عليه بالفشل، ويمكن عكس أي وظيفة بسهولة. إن الدالة أحادية الاتجاه المستندة إلى مدى صعوبة هذه المشكلة هي الوظيفة الأكثر أمانًا الممكنة - وهي دالة ذات اتجاه واحد للتحكم فيها جميعًا.

البناء على هياكل البيانات

كان اكتشاف باس وليو هو الفصل الأخير في سلسلة طويلة من الأبحاث التي تستخدم نظرية التعقيد لفهم أسس التشفير بشكل أفضل. ولكنها اقترحت أيضًا طريقة لقلب هذه العلاقة: فالتكافؤ بين مشكلة تعقيد كولموجوروف المحددة زمنيًا وانقلاب الوظيفة يعني ضمنًا أن الرؤى حول أي من المشكلتين يمكن أن تكشف المزيد عن المشكلة الأخرى. لقد ظل علماء التشفير يدرسون خوارزميات انعكاس الوظيفة لعقود من الزمن لفهم نقاط الضعف في طرق التشفير الخاصة بهم بشكل أفضل. بدأ الباحثون يتساءلون عما إذا كانت تلك الخوارزميات يمكن أن تساعد في الإجابة على الأسئلة القديمة في نظرية التعقيد.

مثل العديد من المشاكل الحسابية، يمكن حل انعكاس الدالة عن طريق البحث الشامل. بالنظر إلى سلسلة الإخراج، ما عليك سوى إدخال كل المدخلات الممكنة في الوظيفة حتى تجد المدخلات التي تعطي الإجابة الصحيحة.

في عام 1980، بدأ عالم التشفير مارتن هيلمان بدراسة ما إذا كان من الممكن القيام بأي شيء أفضل، وهو نفس السؤال الذي طرحه علماء الرياضيات السوفييت حول مشاكل الضغط قبل عقود. رجل الجحيم اكتشف نعم، هذا ممكن، طالما أنك على استعداد لبذل بعض العمل الإضافي مسبقًا، باستخدام كائنات رياضية تسمى هياكل البيانات.

بنية البيانات هي في الأساس جدول يخزن معلومات حول الوظيفة المراد عكسها، ويتطلب إنشاء واحدة حساب مخرجات الوظيفة لبعض المدخلات المختارة بشكل استراتيجي. وقال إن كل هذه الحسابات "قد تستغرق وقتا طويلا جدا". ريان ويليامز، منظر التعقيد في معهد ماساتشوستس للتكنولوجيا. "لكن الفكرة هي أن يتم ذلك مرة واحدة وإلى الأبد." إذا كنت تحاول عكس نفس الوظيفة في ضوء العديد من المخرجات المختلفة - على سبيل المثال، فك تشفير العديد من الرسائل المختلفة المشفرة بنفس الطريقة - فقد يكون القيام بهذا العمل مقدمًا مفيدًا.

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

بعد الإنجاز الذي حققه باس وليو في عام 2020، أصبحت هذه النتائج القديمة فجأة ذات أهمية جديدة. يمكن لخوارزمية Fiat-Naor عكس الوظائف التعسفية بشكل أسرع من البحث الشامل. هل يمكن أن يعمل أيضًا على حل مشكلات الضغط؟

خارج الزي الرسمي

كان الباحثون الأوائل الذين طرحوا هذا السؤال هم أصحاب نظرية التعقيد راهول سانتانام من جامعة أكسفورد وطالب الدراسات العليا هانلين رن. لقد فعلوا ذلك في أ ورقة 2021 مما يثبت أن مشاكل الضغط وانعكاس الوظيفة كانت أكثر تشابكًا مما أدركه الباحثون.

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

كان لنتائجهم آثار مختلفة على فئتين عريضتين من الخوارزميات التي يدرسها الباحثون غالبًا، والتي تسمى الخوارزميات "الموحدة" و"غير الموحدة". تتبع الخوارزميات الموحدة نفس الإجراء لكل إدخال - على سبيل المثال، سيعمل برنامج موحد لفرز قوائم الأرقام بنفس الطريقة سواء كان هناك 20 إدخالًا في القائمة أو 20,000. بدلاً من ذلك، تستخدم الخوارزميات غير المنتظمة إجراءات مختلفة للمدخلات ذات الطول المختلف.

إن هياكل البيانات التي تستخدمها خوارزمية Fiat-Naor مصممة دائمًا لوظيفة محددة. لعكس دالة تقوم بتشفير سلسلة مكونة من 10 بتات، تحتاج إلى بنية بيانات مختلفة عن تلك التي تحتاجها لعكس دالة تقوم بتشفير سلسلة مكونة من 20 بت، حتى لو تم إجراء التخليط بطريقة مماثلة. وهذا يجعل من فيات-ناور خوارزمية غير موحدة.

تشير نتيجة سانتانام ورين إلى أنه قد يكون من الممكن تحويل خوارزمية فيات-ناور إلى خوارزمية لحل مشاكل الضغط. لكن تكييف الخوارزمية من مشكلة إلى أخرى لم يكن سهلاً، ولم يتابعوا السؤال أكثر.

وعثر باس على نفس الفكرة بعد مرور عام، بعد أن سمع شركة فيات تتحدث عن الخوارزمية الكلاسيكية في ورشة عمل تحتفل بمساهمات ناعور في التشفير. وقال: "إن فكرة استخدام انعكاس الوظيفة كانت في ذهني منذ ذلك الحين". بدأ لاحقًا العمل على المشكلة بشكل جدي مع باحث في جامعة تل أبيب نعوم مازور.

في هذه الأثناء، استلهم إيلانجو مهاجمة المشكلة بعد مناقشات مع باحثين آخرين، بما في ذلك سانتانام، أثناء زيارة إلى معهد سيمونز لنظرية الحوسبة في بيركلي، كاليفورنيا. قال سانتانام: "لقد جاء ذلك من إحدى هذه المحادثات الصدفة للغاية حيث تقوم فقط برمي الأشياء". انضم إيلانجو لاحقًا إلى ويليامز و شويتشي هيراهارا، أحد منظري التعقيد في المعهد الوطني للمعلوماتية في طوكيو.

كان الجزء الصعب هو معرفة كيفية دمج بنية البيانات الموجودة في قلب خوارزمية Fiat-Naor في خوارزمية غير موحدة لحل مشكلات الضغط. هناك إجراء قياسي للقيام بهذا النوع من التضمين، لكنه قد يؤدي إلى إبطاء الخوارزمية، مما يؤدي إلى محو ميزتها على البحث الشامل. وجد الفريقان طرقًا أكثر ذكاءً لدمج بنية بيانات Fiat-Naor، وحصلا على خوارزميات لمشكلات الضغط التي عملت على جميع المدخلات وظلت أسرع من البحث الشامل.

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

التقارب الانعكاسي

يثير الدليل الجديد للخوارزميات غير المنتظمة سؤالاً طبيعيًا: ماذا عن الخوارزميات الموحدة؟ هل هناك طريقة لحل مشكلات الضغط بشكل أسرع من البحث الشامل باستخدامها؟

وتشير سلسلة النتائج الأخيرة إلى أن أي خوارزمية من هذا القبيل ستكون معادلة لخوارزمية موحدة لعكس الوظائف العشوائية، وهو الأمر الذي سعى إليه علماء التشفير دون جدوى لعقود من الزمن. ولهذا السبب، يرى العديد من الباحثين أن هذا الاحتمال غير مرجح.

قال سانتانام: "سأكون مندهشًا للغاية". "سيتطلب الأمر فكرة جديدة تمامًا."

لكن ألندر قال إنه لا ينبغي للباحثين استبعاد هذا الاحتمال. وقال: "كانت فرضية العمل الجيدة بالنسبة لي هي أنه إذا كانت هناك طريقة غير موحدة للقيام بشيء ما، فمن المحتمل جدًا أن تكون هناك طريقة موحدة".

وفي كلتا الحالتين، أدى هذا العمل إلى جعل منظري التعقيد مهتمين حديثًا بالأسئلة القديمة في مجال التشفير. يوفال إشاي، وهو متخصص في التشفير في التخنيون في حيفا، إسرائيل، قال إن هذا ما يجعل الأمر أكثر إثارة.

وقال: "أنا سعيد حقاً برؤية هذا التقارب في المصالح بين المجتمعات المختلفة". "أعتقد أنه أمر رائع للعلوم."