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

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

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

ف NP

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

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

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

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

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

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

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

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

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

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

الكشف عن أسرار تعقيد الخوارزميات

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

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

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

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