مسائل NP صعبة

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

تعريف

لتكن ${\displaystyle A\subseteq \{0,1\ ^{*$ لغة، نقول انها NP صعبة إذا : لكل لغة ${\displaystyle L\in NP$ يمكن اختصار ${\displaystyle L$ ل- ${\displaystyle A$ ,اي: ${\displaystyle L\leq _{p A$ اي يوجد دالة ${\displaystyle f:\{0,1\ ^{* \to \{0,1\ ^{*$ بحيث انه يمكن حساب ${\displaystyle f$ بوقت حدودي وكذلك يتحقق التالي : ${\displaystyle x\in L\iff f(x)\in A$ .

امثلة

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

انظر أيضا

قسم تعقيد
نظرية التعقيد الحسابي.
مسألة P=NP
خوارزمية
مشكلة إعادة جدولة السيارة

مراجع

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