كتب صياغة التساؤلات
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
صيغة المسألة (معلومة)
المسالة P = NP هي تحديد إذا ما كل مسألة يمكن تقريرها بواسطة خوارزمية غير قطعية يمكن أيضا حلها بواسطة خوارزمية قطعية . حتى نستطيع تعريف المسألة بشكل دقيق يجب علينا تحديد نموذج حاسوبي . النموذج الأساسي للحاسوب في النظرية الحاسوبية هي آلة تورنغ والتي عرفها آلان تورنغ عام 1936 و بالرغم من أن هذا النموذج ظهر قبل الحاسوب الذي نعرفه الٱن لكنه أنموذج مقبول نظر لأساسيته الهادفة والثابتة الهدف أجلا وأملا في تعريف المصطلح كدالة قابلة للحساب .
تقديم آلة تورنج كان أحد أهم الخطوات في جعل الحاسوب نموذجا رياضيا والأهم من هذا باتت قدرتنا ٱنيا تتيح لنا إعطاء تعريف دقيق للقسم أو الصنف P بالإضافة للصنف المضاد NP , ولكن تنقص بعض التعريفات المهمة منها تعريف لغة آلة تورنج بشكل غير رسمي هي كل المُداخلات التي تنمذجها آلة تورنج والتي دورها تقديم صواب الجواب ب "نعم" و بشكل دقيق ونعرفها كالٱتي : فلتكن M آلة تورنج، ولنفترض أنَّ هي أبجدية الآلة (ٱلة تورنغ) حينها نعرف لغة الآلة أنها كالتالي: .
نجاعة الخوارزمية في هذه الحالة هي كمية الوقت التي تستخدمها الخوارزمية حتى الوصول للنتيجة الدقيقة : فلتكن دالة من الأعداد الطبيعية إلى الأعداد الطبيعية (نسميها في مثير من الأحيان دالة وقتية أو دالة الوقت) حينها نرمز ل- هي مجموعة كل المسائل التي توجد آلة تورنج على متنها محتمة وتحلها خلال و عدد خطوات الحساب التي تلزم الآلة للوصول لصواب الجواب حيث نستطيع أيضا وبشكل مشابه تعريف لكن الأنموذج يبرز ٱلة تورنج الغير حتمية .
من التعريفين السابقين صيغة المسألة بشكل دقيق ستكون كالتالي : نعرف P لتكون , ونعرف NP ليكون , والسؤال هو هل هاتين المجموعتين متساويتين ؟
بما أن السؤال هو تساوي المجموعتين علينا أن نعرف إذا ما أن P تحوي NP وأيضا هل NP تحوي P أم أنهما غير ذلك وفي إطار أحد هذين الاحتواءين من السهل البرهنة على صواب الجواب ودقيقه وهو أنَّ P تحوي NP بشكل غير رسمي: لأن كل آلة حتمية هي آلة غير حتمية ولكن لا تستخدم قدرتها على أن تكون غير حتمية أو حتمية.
المسألة الصعبة والتي لا برهان لها هي الاحتواء الثاني (أي احتواء NP على P ) لذا فان المسألة هي هل NP تحوي المجموعة P أم أن الأمر غير ذلك ؟ لنفترض أن المجموعة الأولى هي {1,2,3,4}وفيها الرقم 2 كمحتوى على متنها ولكن احتواء المجموعة الثانية للرقم 2 ليس احتواء شاملا سوى للرقمين 1,2 و بالتالي :NP ليست تساوي P .
