تطوير MIT أداة جديدة لمعالجة مشاكل الحوسبة الصعبة

قام David Jamarnik بتطوير أداة جديدة، Overlap Gap Properties، لفهم مشاكل حسابية تبدو مستعصية على الحل.

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

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

P ≠ NP

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

على الرغم من أن التخمين بأن P ≠ NP لم يتم إثباته، يعتقد معظم علماء الكمبيوتر أن العديد من المشكلات المألوفة (على سبيل المثال، مشكلة البائع المتجول) تقع ضمن هذه الفئة الصعبة للغاية. يتمثل التحدي في مثال البائع في العثور على أقصر مسافة أو طريق زمني عبر مدن مختلفة. يمكن إدارة المهام إنه أمر سهل مع قيمة N = 4، نظرًا لوجود ستة مسارات فقط يمكن وضعها في الاعتبار. لكن بالنسبة لـ 30 مدينة، يوجد أكثر من 1030 طريقًا محتملاً، ويزداد العدد بشكل كبير من هناك. تكمن الصعوبة الأكبر في ابتكار خوارزمية تحل المشكلة بسرعة في جميع الحالات، لجميع قيم الأعداد الصحيحة للمادة N. عالم الحاسوب بناءً على نظرية التعقيد الحسابي، فهم مقتنعون بعدم وجود مثل هذه الخوارزمية، وبالتالي يؤكدون أن P ≠ NP.

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

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

قمم ووديان

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

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

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

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

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

كشف أسرار التعقيد الحسابي

يمكن أن يساعد ظهور هذا البرنامج الباحثين في تقييم صعوبة إنشاء خوارزميات سريعة لحل مشكلات معينة. قال جامارنيك إن هذا سمح لهم باستبعاد [و] عدد كبير من الخوارزميات كمنافسين محتملين. على وجه التحديد، تعلمنا أن الخوارزمية المستقرة هي خوارزمية لا يتغير ناتجها كثيرًا إن لم يتغير غيّر قليلاً فقط - لن تتمكن من حل مشكلة التحسين هذه. لا تنطبق هذه النتيجة السلبية على أجهزة الكمبيوتر الكلاسيكية فحسب، بل تنطبق أيضًا على أجهزة الكمبيوتر الكمومية، ولا سيما ما يسمى بخوارزمية تحسين النهج الكمي (QAOA)، والتي كان بعض الباحثين يأملون في حل مشكلات التحسين نفسها. الآن، بالنظر إلى النتائج التي توصل إليها Jamarnik والمؤلفون المشاركون معه، فقد تضاءلت هذه الآمال بسبب إدراك أن مستويات متعددة من العمليات مطلوبة لجعل خوارزميات نمط Kawa تعمل، وهو ما يمثل تحديًا تقنيًا.

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

 يساعدنا في فك ألغاز التعقيد الحسابي وتحسين فهمنا لعالم الاحتمال. هذه أخبار سيئة لأنها تخبرنا أن هذه

 المشاكل صعبة، حتى لو ظهرت بشكل طبيعي، حتى لو تم حلها تم إنشاؤه بشكل عشوائي. وأضاف أن الأنباء

 لم تكن مفاجأة. توقع الكثير منا هذا منذ البداية، ولكن لدينا الآن أساس أقوى لتقديم هذا الادعاء.

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

إن توقع المدة التي ستستغرقها هذه العملية قبل حل مشكلة P ≠ NP هي مشكلة صعبة في حد ذاتها. قد يكون هناك المزيد من القمم لتسلقها والوديان لاجتيازها قبل أن يتمكن الباحثون من الحصول على صورة أوضح.