يطور الباحث أداة جديدة لفهم مسائل التفاضل والتكامل الصعبة التي تبدو مستعصية على الحل

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

يركز David Gamarnik ، أستاذ أبحاث العمليات في كلية MIT Sloan للإدارة ومعهد البيانات والأنظمة والمجتمع ، اهتمامه على هذه الفئة الأخيرة من المشكلات الأقل دراسة والتي تكون أكثر صلة بالعالم. أنها تنطوي العشوائية– سمة لا يتجزأ من النظم الطبيعية. طور هو وزملاؤه أداة قوية لتحليل هذه المشكلات تسمى خاصية التداخل (أو OGP). وصف Gamarnik المنهجية الجديدة في مقال حديث لـ وقائع الأكاديمية الوطنية للعلوم.

ف NP

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

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

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

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

القمم والوديان

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

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

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

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

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

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

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

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

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

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