ان‌پی سخت

Euler diagram for P, NP, ان‌پی کامل, and NP-hard set of problems
مجموعه « ان‌پی-سخت » شامل چندهزار مسئله مختلف با کاربردهای فراوان است که تاکنون برای آن‌ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده‌است و به احتمال زیاد در آینده نیز یافت نخواهد شد.این که راه حل سریعی برای آن‌ها وجود ندارد هم اثبات نشده‌است.البته ثابت شده‌است که اگر فقط برای یکی از این مسئله‌ها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیه مسئله‌ها خواهد شد.البته احتمال پیدا شدن چنین الگوریتمی ضعیف است.منظور از راه حل سریع آن است که زمان اجرای آن با اندازه ورودی مسئله به صورت چندجمله‌ای رابطه داشته باشد.
ریشه انگلیسی
ان پی-سخت: Non-deterministic Polynomial-time hard)→NP-hard)
حل نشدنی درزمان چندجمله‌ای بر حسب اندازه ورودی مسئله (زمان معقول)
مفهوم و مقایسه آن با ان پی-کامل
مسئله H ان پی-سخت است اگر و فقط اگر مسئله L از نوع ان پی-کامل موجود باشد ٫ به‌طوری‌که زمان حل آن بر حسب چندجمله‌ای قابل کاهش به Hباشد: (L ≤ T H)به عبارتی دیگر L را میتوان در زمان زیاد با ماشین اوراکل H حل کرد.به‌طور غیررسمی ما میتوانیم به الگوریتمی فکر کنیم که می‌تواندزیرروالی را برای حل H فراخوانی کند و L را در زمان زیاد حل کند اگر فراخوانی آن زیر روال فقط یک گام برای محاسبه طول بکشد.
مسائل ان پی-سخت ممکن است از هر نوعی باشند:مسائل تصمیم گیری٫مسائل جستجو٫مسائل بهینه سازی.
طبق روال تعریف: (توجه داشته باشید که اینها صرفا ادعا هستند نه تعریف):
مسئله H حداقل به سختی مسئله L است. چون H می‌تواند برای حل L استفاده شود.
چون L ان پی-کامل است ٫بنابراین به سختی مسائل نوع ان پی است. مسئله H حداقل به سختی مسئله ان پی است.اما H نباید ان پی باشد و بنابراین نباید از نوع مسائل تصمیم گیری باشد(حتی اگر از نوع مسایل تصمیم‌گیری باشد نیازی ندارد ازنوع مسائل ان پی باشد.)
مسائل ان پی-کامل با زمان زیاد با ۱ واحد کاهش به یکدیگر تبدیل می‌شوند(همچنین تحولات چند جمله‌ای نیز نامیده می‌شوند.)
همه مسائل ان پی-کامل با کاهش H میتوانند در زمان زیاد حل شوند.بنابراین همه مسائل در ان پی قابل کاهش به H هستند.توجه داشته باشید هر چند این شامل ترکیب کردن ۲ تبدیل است:
از مسائل تصمیم گیری به مسائل ان پی-کامل با تحولات چندجمله‌ای
از L به H با کاهش چند جمله‌ای تورینگ. ماشین_تورینگ
اگر یک الگوریتم چندجمله‌ای برای هر مسئله ان پی-سخت موجود باشد٫ سپس الگوریتمهای چندجمله‌ای برای همه مسائل در ان پی وجود دارند و بنابراین مسئله برابری پی و ان‌پی
اگر P ≠ NP باشد ٫ مسائل ان پی-سخت راه حلی در زمان‌های زیاد ندارند.زمانی که مسئله برابری پی و ان‌پی باشد ٫ مسائل حل نمی‌شوند.حتی اگر مسائل ان پی-سخت بتوانند در زمان زیاد حل شوند.
اگر مسائل بهینه سازی ٫H یک نسخه تصمیم‌گیری ان پی-کامل داشته باشند٫ H یک ان پی-سخت است.
یک اشتباه رایج این است که فکر می‌کنیم ان پی در ان پی-سخت بر پایه غیر چند جمله‌ای است. اگر چه به‌طور گسترده انتظار میرود که هیچ الگوریتم غیر چند جمله‌ای بر حسب تابع زمانی برای مسائل ان پی- سخت وجود ندارد ولی این موضوع هنوز اثبات نشده‌است. علاوه بر این مسائل از نوع ان پی همچنین شامل همه مسائلی هستند که میتوانند در چندجمله‌ای از تابع زمان حل شوند.
روش حل مسایل ان پی-سخت
روش‌های مختلفی برای حل سریع ولی نزدیک به بهینه برای یک مسئله ان پی-سخت وجود دارد:
راه حل تقریبی قابل اثبات ( الگوریتم‌های تقریبی ):که در آن یک الگوریتم سریع برای حل مسئله ارائه می‌شود ولی اثبات می‌شود که اندازه خروجی ضریبی از اندازه خروجی بهینه مسئله‌است.
الگوریتم‌های مکاشفه‌ای :با این که الگوریتم‌هایی سریع هستند و به صورت تقریبی جواب را به دست می‌آورند٫اما در مورد ضریب تقریب یا میزان خوبی الگوریتم اثباتی وجود ندارد.بسیاری از این الگوریتم‌ها به صورت تجربی آزمایش می‌شوند.برخی از این الگوریتم‌ها از «روش حریصانه» برای حل استفاده می‌کنند.
الگوریتم‌ها
راه‌های معمول مقابله با چنین مسائلی عبارتند از:
طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آن‌ها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
استفاده از «الگوریتم‌های مکاشفه‌ای»(Heuristic) که جواب‌هایی به‌دست می‌دهد که احتمالا درست هستند.
پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.
نمونه مسائل ان پی-سخت
مسئله فروشنده دوره‌گرد
مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل) (maximum clique problem)