هل P =NP ؟
إنها المسألة الثالثة ضمن لائحة معهد كلاي للمسائل الرياضية غير المحلولة، وضعها “ستيفن كوك” عام 1971، وهي أكثر مسألة يمكن لشخص عادٍ أن يحلها، كونها لاتستدعي معارف رياضية معمقة. يتعلق الأمر بمسألة في المعلوميات النظرية أكثر منها في الرياضيات المجردة.
بإمكاننا القول، على نحو مبسط، إن المسألة متعلقة بالحواسيب بمدى فعاليتها في الوصول إلى حل مجموعة متسلسلة من العمليات. وبعبارة أوضح: تتعلق بإيجاد حلول برمجية – خوارزميات- لحل المشاكل الرياضية. فنحن نكتب للحاسوب برامج على هيئة خطوات متسلسلة تصل في النهاية إلى ناتج هو حل للمسألة. لكن هناك مسائل أعقد من غيرها. بعض هذه المسائل قد لا يكون لها حل، وبعضها قد يكون لها حل لكن ليس في وقت خطّي polynomial-time. وهذا يعني أننا نكتب للمشكلات البسيطة برامج تنتهي في وقت معقول وتصل بنا للنتيجة الحسابية. من هنا إذًا يتراءى لنا نوعان من المسائل
ـ مسائل P : هي مسائل ذات طول معقول يمكن التوصل الى حلها من خلال الخوارزميات، وذلك في مدة زمنية طويلة جدا (مثلا للبرهنة على ان عددا ما أولي ( أي أنه لا يقبل القسمة إلا على نفسه)، يتطلب ذلك القيام بقسمات متتالية لهذا العدد على الأعداد الأولية التي تصغره للتأكد من عدم وجود قواسم اخرى.
ـ مسائل NP : هي مسائل تصعب البرهنة عليها، بحيث يكون شبه مستحيل التوصل الى حل لها، في حين يكون إيجاد حلول بديهية سهلا جدا، و بالتالي تكون الإجابة عن هذا النوع من المسائل فقط من خلال التحقق
من الحلول. و لتقريبكم من التعريف، إليكم المثال التالي: المطلوب هو إيجاد الأعداد التي تحقق العلاقة التالية:
X²+y²=z²
أمر صعب، لكن التحقق من الحلول أمر في منتهى السهولة x و y z كما تلاحظون إيجاد صيغة
أمامنا إذا مجموعتان. إن السؤال هو تساوي مجموعتين. علينا أن نعرف إذا ما كانت إحدى المجموعتين تقع ضمن الأخرى:
هل p ضمن NP ؟
هل Np ضمن p ؟
إن هذه المسألة التي أبت أن تستجيب لمحاولات الباحثين في إثباتها كفيلة بإحداث نقلة نوعية في جميع المجالات.
إن التوصل الى برهان ينفي او يثبت هده المتساوية سوف يغير الكثير من القناعات في مجال الحاسوب وسيمكن من حل مجموعة من المشاكل مثل فك تشفير الحماية السرية في الأنترنت و مشكلة التنبؤ ببنية البروتين التي قد تحدث تقدما كبيرا في علم البيولوجيا، وهذا سيغير الحياة التي سنعرفها الى الأبد. فلهذا توابع مذهلة تصل الى درجة الخيال، لأنه بعد أن يتم إثبات المسألة ستكون الحياة أسهل و مثالية، إذ لن نكون بحاجة لرياضيين ليبرهنوا لنا الحدسيات، بحيث سيتم تعويضهم ببرامج معلوماتية تحاكي عقولهم، كما أن تصميمات الذكاء الاصطناعي ستكون دقيقة، ولسنا بحاجة الى أي نوع من التقريب. من سيتمكن من حل هذه المسألة إذًا سيخرج من معهد كلاي ليس فقط بمليون دولار، بل بخمسة ملايين دولار، حيث إن إثباته سيجعل المسائل الاخرى بديهية.
p=NP تعدت المعلوميات والرياضيات والبيولوجيا إلى الفلسفة، حيث إن السؤال هو: هل p مقابلNP
يمكن تأويله بصيغة أخرى؟
هل كل ما يمكننا إيجاده بسرعة بواسطة الحظ يمكننا إيجاده بسرعة بواسطة الحساب الذكي؟
باختصار، هل الذكاء يمكن ان يعوض الحظ؟
هل كل ما يمكننا التحقق منه بسهولة يمكن البرهنة عليه بسهولة؟
لتوضيح هذه المفارقة إليكم المثال التالي:
مثال مسار هاملتون الشهير
التحقق من أن مسارا ما في رسم ثلاثي الأبعاد يمر من كل العقد الموجودة بهذا الرسم دون المرور بإحداها مرتين أمر سهل،ولكن البحث عن هذا المسار يكاد يكون أمرا مستحيلا، إذ لا توجد أية خوارزمية تمكننا من ذلك.
P =NP
ترى أين و متى وعلى يد من ستحل هذه الأحجية الغامضة لتتحول من حدسية الى نظرية؟
اعداد نورة ابليق
التدقيق اللغوي: علي توعدي
الكاتب:
