مسألة P=NP
إن العلاقة بين مسائل التعقيد P ومسائل NP الكاملة هي مسألة غير محلولة في المعلوماتية النظرية. وهي تعتبر من أهم المسائل في هذا الحقل وقد عرض معهد كلاي للرياضيات جائزة مقدارها مليون دولار أمريكي لأول برهان صحيح لهذه المسألة.
جوهر المسألة في أنه إذا كان من الممكن التأكد من الجواب الصحيح لمسألة ما بعد الحصول عليه في الزمن الخطي فهل من الممكن أيضاً حساب هذه الأجوبة ذاتها بسرعة؟
خذ على سبيل المثال مسألة مجموع المجموعات الجزئية، وهو مثال على مسألة من السهل التحقق من صحة جوابها، لكن عملية حساب الجواب نفسه يعتبر (هذا الأمر غير مبرهن بعد) من الأمور الصعبة. على سبيل المثال هل يوجد مجموعة جزئية من المجموعة التالية {−2, −3, 15, 14, 7, −10} يكون مجموع عناصرها مساوياً للصفر؟ الجواب بكل بساطة هو نعم، لأن المجموعة الجزئية {−2, −3, −10, 15} مجموعها صفر وهو أمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إن عملية إيجاد كل مجموعة جزئية من المجموعة الأساسية يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتاً طويلاً.
انظر أيضاً
| ملف:Nuvola apps edu mathematics-ar.svg | هذه بذرة مقالة عن الرياضيات تحتاج للنمو والتحسين، فساهم في إثرائها بالمشاركة في تحريرها. |
| ملف:Nuvola apps edu mathematics-ar.svg | بوابة رياضيات تصفح مقالات ويكيبيديا المهتمة بالرياضيات. |
ca:P versus NP cs:Problém P versus NP de:P-NP-Problem P versus NP problem]] eo:Demando P = NP es:Clases de complejidad P y NP fa:مسئله برابری پی و انپی fi:P=NP fr:Problème P = NP it:Classi di complessità P e NP ja:P≠NP予想 ko:P-NP 문제 pt:P versus NP ru:Равенство классов P и NP simple:P versus NP sr:П = НП проблем sv:P=NP? th:กลุ่มความซับซ้อน พี และ เอ็นพี tr:P ile NP arasındaki ilişki uk:Рівність класів P і NP zh:P/NP问题
