NP-صعب

تُعد فئة NP-صعب (NP-Hard) فئة أساسية في نظرية التعقيد الحاسوبي، وتضم المسائل التي يمكن اختزال كل مسألة في NP إليها في زمن كثير الحدود. أرسى المفهوم Cook (1971) بإثبات أن مسألة تحقق العبارات البوليانية (SAT) هي NP-كاملة، ثم Karp (1972) بإثبات NP-كمال إحدى وعشرين مسألة تجميعية عبر اختزالات كثيرة الحدود، مما رسّخ الفئة في بحوث العمليات العملية. المسألة التي تنتمي إلى NP وتكون NP-صعب في آن واحد تسمى NP-كاملة؛ إن لم تكن في NP فقد تظل NP-صعب (مثل نسخة التحسين من TSP). تشمل المسائل NP-صعب الكلاسيكية: البائع المتجول (TSP)، حقيبة الظهر، تلوين الرسوم البيانية، التغطية، توجيه المركبات، جدولة job shop، تقليل المدة الإجمالية، التعبئة في صناديق، والعديد من صياغات البرمجة العددية الصحيحة المختلطة (MIP). يظل سؤال P = NP مفتوحاً رياضياً؛ عملياً، كل خوارزمية دقيقة معروفة لمسائل NP-صعب تتطلب زمناً أسياً في حجم المدخل. دفع هذا إلى تطوير الإرشاديات وميتا-إرشاديات وخوارزميات التقريب. Garey وJohnson (1979) المرجع الأساسي لبراهين NP-كمال. تصنيف مسألة NP-صعب إشارة حاسمة للممارس بترك توقع الحل الدقيق المباشر واختيار الإرخاء أو التحليل أو المقاربات الإرشادية.