المشكلة البالغة من العمر 50 عامًا والتي تستعصي على علوم الكمبيوتر النظرية

يمكن أن يؤدي حل P vs NP إلى حل مشكلات حسابية لا حصر لها - أو إبقائها بعيدة المنال إلى الأبد.



مشكلة شجرة شتاينر: قم بتوصيل مجموعة من النقاط بأجزاء الخط ذات الطول الإجمالي الأدنى.

مشكلة شجرة شتاينر: قم بتوصيل مجموعة من النقاط بأجزاء الخط ذات الطول الإجمالي الأدنى.ديريك براني

27 أكتوبر 2021

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





كم من الوقت للتغلب على لعبة أوزة بلا عنوان

اثنين سعيد.

قضية الحوسبة

كانت هذه القصة جزءًا من إصدارنا في نوفمبر 2021

  • انظر إلى بقية القضية
  • يشترك

في عالم موازٍ ، ربما كان يوم الإثنين سعيدًا جدًا حقًا. ظهر دليل على الإنترنت في المجلة المحترمة ACM Transactions on Computational Theory ، والتي تتداول في البحث الأصلي المتميز الذي يستكشف حدود الحساب الممكن. النتيجة المزعومة لحل مشكلة جميع المشاكل - الكأس المقدسة لعلوم الكمبيوتر النظرية ، التي تبلغ قيمتها مليون دولار جائزة والشهرة التي تنافس أرسطو إلى الأبد.



هذه المشكلة العزيزة - المعروفة بـ P مقابل NP - تعتبر في الحال الأكثر أهمية في علوم الكمبيوتر النظرية والرياضيات وهي بعيدة المنال تمامًا. يتناول أسئلة مركزية في الوعد والقيود والطموحات الحسابية ، ويسأل:

لماذا بعض المشاكل أصعب من غيرها؟

ما هي المشاكل التي يمكن أن تحلها أجهزة الكمبيوتر بشكل واقعي؟

كم من الوقت سوف يستغرق؟



وهي مهمة ذات مكاسب فلسفية وعملية كبيرة.

انظر ، سؤال P مقابل NP ، ماذا يمكنني أن أقول؟ كتب سكوت آرونسون ، عالم الكمبيوتر بجامعة تكساس في أوستن ، في كتابه مذكرات الأفكار و الحوسبة الكمية منذ ديموقريطس . يحب الناس وصفها بأنها 'على الأرجح المشكلة المركزية التي لم يتم حلها لعلوم الكمبيوتر النظرية'. يعد P vs NP أحد أعمق الأسئلة التي طرحها البشر على الإطلاق.

تتمثل إحدى طرق التفكير في أبطال هذه القصة في ما يلي:

تمثل P المشكلات التي يمكن للكمبيوتر حلها بسهولة.

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

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

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

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

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

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

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

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

الدعامات

مشكلة البائع المتجول: ابحث عن أقصر طريق ممكن يزور كل مدينة مرة واحدة ، ويعود في النهاية إلى المدينة الأصلية.

ديريك براني

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

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

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

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

الطريقة التي يتعامل بها مع شرح يمكن الوصول إليه لـ P مقابل NP هي مع مشكلة الضرب الأساسية: 7 × 13 =؟

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

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

5003588856 0437213507310 7418240490 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540246 91752206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540246 91752

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

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

أسئلة مثل هذا السؤال تقع في قلب التعقيد الحسابي - حقل مليء بالمشاكل الوحشية التي يحاول الباحثون فهمها. قام آرونسون بتجميع حديقة حيوان معقدة ، وهي كتالوج عبر الإنترنت به 545 فئة من المشكلات (والعد). يتم تصنيف كل منها حسب درجة تعقيدها ، أو صعوبتها ، والموارد - الوقت ، والذاكرة ، والطاقة - اللازمة لإيجاد الحلول. P و NP هي مناطق الجذب الرئيسية.

كما يمكن أن تكون الصدفة العلمية ، فإن عالم الرياضيات السوفيتي ليونيد ليفين التقارب في نتيجة تعادل نتائج كوك في نفس الوقت تقريبًا.

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

على النقيض من ذلك ، قد تكون بعض مشكلات NP الصعبة قابلة للحل فقط عن طريق الخوارزميات مع أوقات التشغيل المحددة بواسطة دالة أسية ، مثل 2 ^ n - إنتاج معدل نمو أسي (كما هو الحال مع انتشار covid). NP ، كما يصفها آرونسون ، هي فئة الآمال المحبطة والأحلام الخاملة. ومع ذلك ، فهو سريع في توضيح مفهوم خاطئ شائع: ليست كل مشاكل NP صعبة. تحتوي الفئة NP في الواقع على الفئة P — لأن المشكلات ذات الحلول السهلة يسهل أيضًا فحصها بالطبع.

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

ومن بين cognoscenti ، يبدو أن هذا هو الإجماع ، والذي يشبهه البعض أكثر بالمعتقد الديني: P ≠ NP. معظمهم لا يسمح إلا بشظية من الأمل في أن العكس سيثبت. يقول آرونسون ، سأعطيها فرصة 2 إلى 3٪ أن P تساوي NP. تلك هي احتمالات الرهان التي كنت سأقبلها.

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

3. في أوائل أغسطس ، عندما قابلت ستيف كوك في مكتبه في الحرم الجامعي ، لم ير أو يسمع عن أحدث لعبة برهان P مقابل NP. الآن 81 ، تقاعد مؤخرًا فقط ، لأن ذاكرته كانت تتخبط. لهذا السبب لدينا جيمس هنا ، كما قال - انضم إلينا ابنه جيمس ، 36 عامًا ، وهو أيضًا عالم كمبيوتر ، في زيارتي. كان ستيف في خضم تصفية مكتبه. وقف صندوق إعادة تدوير عملاق في منتصف الغرفة ، ممتلئًا بقضايا اصفرار قديمة لمجلة Journal of Symbolic Logic ، وهي كومة من دفاتر هاتف تورنتو فائقة الدهون تنتظر في مكان قريب.

على مر السنين ، رأى كوك العديد من البراهين التي تزعم حل مشكلة P مقابل NP. في عام 2000 ، بعد أن أطلق عليها معهد كلاي للرياضيات اسم إحدى مشكلات الألفية السبع التي لم يتم حلها (تبلغ قيمة كل منها جائزة مليون دولار) ، غمرته رسائل من أشخاص اعتقدوا أنهم انتصروا. كل النتائج كانت خاطئة ، إن لم تكن وهمية. ادعى حوالي النصف أنهم أثبتوا أن P تساوي NP ؛ النصف الآخر ذهب في الاتجاه المعاكس. منذ وقت ليس ببعيد ، ادعى شخص واحد أنه أثبت كليهما.

ما مدى دفء جسم الإنسان

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

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

تطور علوم الكمبيوتر كان حساب مستويات الطاقة لذرة الهليوم في عام 1958 أصعب بكثير مما هو عليه اليوم. لكن المقارنة بين الأساليب السابقة والحالية تكشف عن بعض الشذوذات البديهية المضادة حول تأثير علوم الكمبيوتر.

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

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

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

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

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

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

في عام 1967 ، وفقًا لكتاب عن Cook سيصدر من جمعية ماكينات الحوسبة (ACM) ، بينما كان باحثًا في مرحلة ما بعد الدكتوراه في بيركلي ، صاغ ملاحظات الدورة التدريبية التي تحتوي على بذرة نتائجه الكبيرة. لقد توصل إلى صياغة لفئات التعقيد التي أصبحت تُعرف باسم P و NP ، وطرح السؤال عما إذا كانت P تساوي NP. (في نفس الوقت تقريبًا ، كان آخرون ، بمن فيهم عالم الكمبيوتر جاك إدموندز ، المتقاعد الآن من جامعة واترلو ، يدورون حول نفس الأفكار).

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

يحلم معظم منظري التعقيد بشكل أصغر قليلاً ، ويختارون بدلاً من ذلك الأساليب غير المباشرة.

في & تي مكافحة الفيروسات لالروبوت

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

كانت هذه نظرية مهمة: إذا كانت هناك خوارزمية متعددة الحدود للوقت تحل مشكلة الرضا ، فستعمل هذه الخوارزمية كمفتاح هيكلي ، وتفتح الحلول لجميع المشكلات في NP. وإذا كان هناك حل متعدد الحدود لجميع المشكلات في NP ، فعندئذٍ P = NP.

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

وبعد ذلك ، كما تقول القصة ، بعد طوفان من نظرية كوك.

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

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

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

في اكتساح التاريخ الكبير ، يرى Papadimitriou ظاهرة اكتمال NP ومسعى P مقابل NP كمصير لعلوم الكمبيوتر. لأن الصدفة العلمية ستحققها ، تقارب عالم الرياضيات السوفيتي ليونيد ليفين على نتيجة تعادل نتائج كوك في نفس الوقت تقريبًا. ليفين ، الذي يعمل حاليًا في جامعة بوسطن ، قام بعمله خلف الستار الحديدي. بعد أن حظيت باهتمام أوسع (هاجر إلى أمريكا عام 1978) ، أصبحت النتيجة معروفة باسم نظرية كوك ليفين.

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

كرات البلياردو

مشكلة الزمرة: ابحث عن مجموعات في رسم بياني ، مثل مجموعة فرعية معينة من الأصدقاء في شبكة اجتماعية.

ديريك براني

أربعة. على الرغم من أن نصف قرن من العمل لم يسفر عن أي شيء قريب من الحل ، إلا أن بعض النتائج على الأقل تأسر الخيال: ادعت ورقة في عام 2004 إثبات لـ P = NP باستخدام فقاعات الصابون كآلية للحساب التناظري (فيلم صابون ، بشكل طبيعي المحاذاة في تكوين الحد الأدنى من الطاقة ، تحل مشكلة شجرة شتاينر الكاملة NP بطريقة ما).

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

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

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

قدّر ويليامز احتمال أن يكون P NP معتدلاً إلى حد ما بنسبة 80٪. لكن في الآونة الأخيرة ، أعرب بعض الباحثين في هذا المجال عن شكوكهم حول هذا المستوى من اليقين. المزيد والمزيد ، بدأت أتساءل عما إذا كانت P تساوي NP ، كما يقول Toniann Pitassi ، عالم الكمبيوتر في جامعة تورنتو وطالب الدكتوراه السابق في Cook’s. نهجها في الالتفاف حول المشكلة هو دراسة كل من نظائرها الموسعة والمقلصة ، والنماذج الأصعب والأسهل. وتقول إن تعميم السؤال يجعل الأمر أكثر وضوحًا في بعض الأحيان. لكنها لم تحقق الوضوح بشكل عام: يعتقد معظم الناس أن P لا تساوي NP. وأنا لا أعرف. ربما أكون أنا وحدي ، لكني أشعر أنه أصبح أقل وضوحًا أن هذه هي الحقيقة.

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

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

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

الجواب ، على عكس ما هو متوقع ، هو نعم.

يعتقد جيمس أنها ذاكرة مستعارة. بعد اندلاع صدمة هذه النتيجة ، استمتع باكتشاف كيفية تطبيقه على مشكلة معينة - ومتابعة المكان الذي توقف عنده والده.

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

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

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

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

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

قال: تخيل أننا محظوظون ، ويمكننا أن نخرج ألفي سنة أخرى من هذا الكوكب ، على الرغم من الصعاب وعلى الرغم من الغرائب. ونحن لا نحل هذه المشاكل. ما هي النقطة؟!

التقنيات الفعلية

فئة

غير مصنف

تكنولوجيا

التكنولوجيا الحيوية

سياسة التكنولوجيا

تغير المناخ

البشر والتكنولوجيا

وادي السيليكون

الحوسبة

مجلة Mit News

الذكاء الاصطناعي

الفراغ

المدن الذكية

بلوكشين

قصة مميزة

الملف الشخصي للخريجين

اتصال الخريجين

ميزة أخبار معهد ماساتشوستس للتكنولوجيا

1865

وجهة نظري

77 Mass Ave

قابل المؤلف

ملامح في الكرم

شوهد في الحرم الجامعي

خطابات الخريجين

أخبار

انتخابات 2020

فهرس With

تحت القبه

خرطوم الحريق

قصص لانهائية

مشروع تكنولوجيا الوباء

من الرئيس

غلاف القصه

معرض الصور

موصى به