مسألة كثير حدود وكثير حدود غير قطعي: الفرق بين النسختين

المسالة P = NP هي تحديد اذاإذا ما كل مسألة [[خوارزمية|يمكن]]<ref name=":0" /> تقريرها بواسطة [[خوارزمية]] غير قطعية يمكن أيضا حلها بواسطة خوارزمية قطعية . حتى نستطيع تعريف المسألة بشكل دقيق يجب علينا تحديد نموذج حاسوبي . النموذج الأساسي للحاسوب في النظرية الحاسوبية هي [[الة تورنغ]] والتي عرفها [[آلان تورنغ]] عام 1936 و بالرغم من أن هذا النموذج ظهر قبل الحاسوب الذي نعرفه الٱن لكنه أنموذج مقبول نظر لأساسيته الهادفة و الثابتة الهدف أجلا و أملا في تعريف المصطلح كدالة قابلة للحساب .

نجاعة الخوارزمية في هذه الحالة هي كمية الوقت التي تستخدمها الخوارزمية حتى الوصول للنتيجة الدقيقة : فلتكن <math> f:\mathbb{N} \to \mathbb{N} </math> دالة من الأعداد الطبيعية إلى الاعدادالأعداد الطبيعية (نسميها في مثير من الأحيان دالة وقتية أو دالة الوقت) حينها نرمز ل- <math> \mbox{DTIME}[f(n)]</math> هي مجموعة كل المسائل التي توجد آلة تورنج على متنها محتمة و تحلها خلال <math>f(n)</math> و عدد خطوات الحساب التي تلزم الآلة للوصول لصواب الجواب حيث نستطيع أيضا و بشكل مشابه تعريف <math> \mbox{NTIME}[f(n)] </math> لكن الأنموذج يبرز ٱلة تورنج الغير حتمية .

بما أن السؤال هو تساوي المجموعتين علينا اطانأن نعرف إذا ما أن P تحوي NP وأيضا هل NP تحوي P أم أنهما غير ذلك و في إطار أحد هذين الإحتواءين من السهل البرهنة على صواب الجواب و دقيقه و هو أنَّ P تحوي NP بشكل غير رسمي : لأن كل آلة حتمية هي آلة غير حتمية ولكن لا تستخدم قدرتها على أن تكون غير حتمية أو حتمية .

المسألة الصعبة والتي لا برهان لها هي الإحتواءالاحتواء الثاني (أي احتواء NP على P ) لذا فان المسألة هي هل NP تحوي المجموعة P أم أن الأمر غير ذلك ؟