مسائل NP صعبة
في البداية، مسائل NP صعبة في علم التعقيد الحسابي هي مجموعة مسائل حيث انه يمكن اختصار كل المسائل في NP اليها. ولهذه المجموعة اهمية عظيمة في علم الحاسوب والرياضيات لما لها من تاثير على كثير من النواحي العملية فيه إذ انه تمتد هذه المجموعة لمسائل التخطيط ومعالجة الصور الرقمية وتحسين مُصرف... ملاحظة: بشكل عام NP كاملة ≠ NP صعبة لذا يجب الاخذ بالحسبان انه إذا NP P فهذا لا يعني بالضرورة أنَّ كل المسائل التي هي NP صعبة كذلك يمكن حلها بوقت حدودي (أي انها تابعة ل- P). وفيما يلي تفاصيل أوسع عن ذلك.
امثلة
وفي السياق ذاته، مسألة التوقف (Halt problem) هي NP صعبة ولكن ليست NP كاملة لانها ليست تابعة ل-NP .
انظر كذلك
ومن ناحية أخرى، مسألة TQBF , هي كذلك NP صعبة ولكن غير معلوم إذا ما هذه المسألة تابعة ل-NP ومثلها مسألة أحجية ن.
وفي هذا الصدد، مُعظم مسائل البحث هي NP صعبة مثل: ايجاد المسار الأثقل في مخطط، ايجاد حل لمسألة حقيبة الظهر.
ومن ناحية أخرى، كل لغة تابعة للمجموعة أو القسم NP كاملة هي كذلك NP صعبة والعكس ليس صحيح.
تعريف
إضافةً إلى ذلك، لتكن لغة، نقول انها NP صعبة إذا: لكل لغة يمكن اختصار ل- , أي: أي يوجد دالة بحيث انه يمكن حساب بوقت حدودي وكذلك يتحقق التالي: .
قسم تعقيد
- نظرية التعقيد الحسابي.
- مسألة P=NP
- خوارزمية
- مشكلة إعادة جدولة السيارة
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟