مسألة P=NP

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

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

خذ على سبيل المثال مسألة مجموع المجموعات الجزئية، وهومثال على مسألة من السهل التحقق من صحة جوابها، لكن عملية حساب الجواب نفسه يعتبر (هذا الأمر غير مبرهن بعد) من الأمور الصعبة. على سبيل المثال هل يوجد مجموعة جزئية من المجموعة التالية {−2, −3, 15, 14, 7, −10 قد يكون مجموع عناصرها مساوياً للصفر،يا ترى؟ الجواب بكل بساطة هونعم، لأن المجموعة الجزئية {−2, −3, −10, 15 مجموعها صفر وهوأمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إذا عملية إيجاد جميع مجموعة جزئية من المجموعة الأساسيةقد يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتاً طويلاً.