مسائل NP صعبة

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث

مسائل NP صعبة في علم التعقيد الحسابي هي مجموعة مسائل حيث انه يمكن اختصار كل المسائل في NP اليها .[1][2][3] ولهذه المجموعة اهمية عظيمة في علم الحاسوب والرياضيات لما لها من تاثير على كثير من النواحي العملية فيه إذ انه تمتد هذه المجموعة لمسائل التخطيط ومعالجة الصور الرقمية وتحسين مُصرف ... ملاحظة : بشكل عام NP كاملة ≠ NP صعبة لذا يجب الاخذ بالحسبان انه إذا NP = P فهذا لا يعني بالضرورة أنَّ كل المسائل التي هي NP صعبة أيضا يمكن حلها بوقت حدودي ( اي انها تابعة ل- P ) .

تعريف[عدل]

لتكن لغة، نقول انها NP صعبة إذا : لكل لغة يمكن اختصار ل- ,اي: اي يوجد دالة بحيث انه يمكن حساب بوقت حدودي وكذلك يتحقق التالي : .

امثلة[عدل]

  • كل لغة تابعة للمجموعة أو القسم NP كاملة هي أيضا NP صعبة والعكس ليس صحيح .
  • مسألة التوقف (Halt problem) هي NP صعبة ولكن ليست NP كاملة لانها ليست تابعة ل-NP .
  • مُعظم مسائل البحث هي NP صعبة مثل : ايجاد المسار الأثقل في مخطط، ايجاد حل لمسألة حقيبة الظهر .
  • مسألة TQBF , هي أيضا NP صعبة ولكن غير معلوم إذا ما هذه المسألة تابعة ل-NP ومثلها مسألة أحجية ن.

انظر أيضا[عدل]

مراجع[عدل]

  1. ^ Daniel Pierre Bovet; Pierluigi Crescenzi (1994). Introduction to the Theory of Complexity. Prentice Hall. صفحة 69. ISBN 0-13-915380-2. الوسيط |CitationClass= تم تجاهله (مساعدة)
  2. ^ Knuth, Donald (1974). "Postscript about NP-hard problems". ACM SIGACT News. 6 (2): 15–16. doi:10.1145/1008304.1008305. مؤرشف من الأصل في 7 مايو 2020. اطلع عليه بتاريخ 30 يناير 2016. الوسيط |CitationClass= تم تجاهله (مساعدة)
  3. ^ "Shtetl-Optimized  » Blog Archive  » The Scientific Case for P≠NP". www.scottaaronson.com. مؤرشف من الأصل في 10 يونيو 2019. اطلع عليه بتاريخ 25 سبتمبر 2016. الوسيط |CitationClass= تم تجاهله (مساعدة)


Nuvola apps edu mathematics-ar.svg
هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. شارك في تحريرها.