ما هي حدسية P=NP؟

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

هناك نوعان من المسائل

مسائل P: تدل على مجموعة المسائل التي لها خوارزمية حل فعالة، مثال ذلك اقسم 340÷5 ، هذا المثال له خطوات معروفة للوصول إلى خارج القسمة.
مسائل NP: تدل على مجموعة المسائل التي ليس لها خوارزمية حل فعالة، ولكن يسهل التحقق من صحة أحد الحلول، مثال ذلك أنا لا أستطيع أن أعرف كل الأعداد التي تحقق هذه المعادلة X²+y²=z² ، ومع ذلك لو أعطيتني ثلاث أرقام كحل، من الممكن أن أتأكد من أن الأرقام حل صحيح للمعادلة أم لا عند تطبيقها على المعادلة.

الكلمات المتقاطعة

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

ما الفائدة من حل الحدسية؟

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

المصادر:

1ـ Claymath

2 ـ Theconversation

3ـ Linternaute