المسالة P ضد NP هي تحديد اذا ما كل مسألة يمكن تقريرها بواسطة خوارزمية غير قطعية يمكن أيضا حلها بواسطة خوارزمية قطعية . حتى نستطيع تعريف المسالةالمسألة بشكل دقيق يجب علينا تحديد نموذج حاسوبي . النموذج الاساسيالأساسي للحاسوب في نظريةالنظرية الحاسوبية هي [[الة تورنغ]] والتي عرفها [[آلان تورنغ]] عام 1936 و بالرغم من انأن هذا النموذج ظهر قبل الحاسوب الذي نعرفه الانالٱن ولكنلكنه هذا النموذجأنموذج مقبول علىنظر انهلأساسيته النموذجالهادفة الاساسيو لهدفالثابتة الهدف أجلا و أملا في تعريف المصطلح دالةكدالة قابلة للحساب .
تقديم آلة تيورنجتورنج كان أحد أهم الخطوات في جعل الحاسوب نموذجا رياضيا والأهم من هذا باتباتت الانقدرتنا بقدرتناٱنيا علىتتيح اعطاءلنا إعطاء تعريف دقيق للقسم اوأو الصنف P والصنفبالإضافة للصنف المضاد NP , ولكن تنقص بعدبعض التعريفات المهمة منها تعريف '''لغة آلة تيورنجتورنج''' بشكل غير رسمي هي كل المُدخلاتالمُداخلات التي تنمذجها آلة تيورنجتورنج تعطيو جوابالتي دورها تقديم صواب الجواب ب "نعم" ,و بشكل دقيق و نعرفها كالتاليكالٱتي : فلتكن M آلة تيورنجتورنج , ولنفرضولنفترض أنَّ <math>\Sigma</math> هي ابجديةأبجدية الآلة ,(ٱلة تورنغ) حينها نعرف لغة الآلة أنها كالتالي: <math> L(M)=\{x\in \Sigma^* : M(x)=1\} </math> .
امر اخر مهم جدا هو نجاعة الخوارزمية , وفيفي هذه الحالة النجاعة هي كمية الوقت التي تستخدمها الخوارزمية حتى الوصول لنتيجةللنتيجة , وبشكل دقيقالدقيقة : فلتكن <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 لتكون <math> \cup_{c>0} DTIME[n^c] </math> , ونعرف NP ليكون <math> \cup_{c>0} NTIME[n^c] </math> , والسؤال هو هل هاتين المجموعتين مساويتانمتساويتين ؟
بما انأن السؤال هو تساوي مجموعتينالمجموعتين علينا اناطان نعرف اذاإذا ما أن P تحوي NP وايضاوأيضا هل NP تحوي P ,أم أنهما غير ذلك و في إطار أحد هذين الاحتواءينالإحتواءين سهلمن انالسهل نبرهنالبرهنة انهعلى يتحققصواب وهوالجواب و دقيقه و هو أنَّ P تحوي NP , بشكل غير رسمي : لانلأن كل آلة حتمية هي آلة غير حتمية ولكن لا تستخدم قدرتها على انأن تكون غير حتمية .أو المسألةحتمية الصعبةوالتي. للان لا برهان لها هو الاحتواء الاخر , لذا فان المسألة هي هل NP تحوي المجموعة P ?لنفرض ان المجموعة الاولى هي{1،2،3،4}وفيها الرقم 2هو محتوا فيها ولكن 2لايحتوي الا 1،2 وبالتالي :NPلا يساوي P
المسألة الصعبة والتي لا برهان لها هي الإحتواء الثاني (أي احتواء NP على P ) لذا فان المسألة هي هل NP تحوي المجموعة P أم أن الأمر غير ذلك ؟
لنفترض أن المجموعة الأولى هي {1،2،3،4}وفيها الرقم 2 كمحتوى على متنها و لكن احتواء المجموعة الثانية للرقم 2 ليس احتواء شاملا سوى للرقمين 1،2 و بالتالي :NP ليست تساوي P .
