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

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

 

 

==صيغة المسألة==

==مسائل كاملة==

من خلال البحث عن اسلوب او طريقة لحل المسألة ظهرت انواع مسائل من نوع اخر , وهذه المسائل كان لها صفتين :

# يمكن تحويل هذه المسائل ما بين بعضها بسرعة .

 

مصطلح الاختصار فتح باباً لتكون لتعريف متى المسائل مطابقة (مع فارق وقت حدودي) , لذا فاننا نعرف المسائل NP كاملة لتكون كل المسائل التي تتبع NP ويمكن اختصار كل المسائل في NP لهذه المسألة , من الوهلة الاولى لا يبدو ان هذه المسائل موجودة وذلك لقوتها الهائلة وذلك لان حلها يعني ان تكون قادرا على حل كثير من المسائل , ولكن المفاجأة انه يوجد مسائل كهذه وهي شائعة وكثيرة ولها كثير من التطبيقات العملية تنبسط على كل مجالات علم الحاسوب تقريبا , ولكن هل يمكن ان نحل هذه المسائل بنجاعة ؟ لا نعرف , وذلك لان هذا السؤال مساوي ومكافئ للسؤال هل NP=P . وبالتحديد يمكن حلها بنجاعة فقط اذا P=NP .

 

 

==توابع جواب الحدسية==