ان‌پی سخت: تفاوت میان نسخه‌ها

مجموعه یمجموعهٔ «'''ان‌پی-سخت'''» شامل چندهزار مساله یمسالهٔ مختلف با کاربردهای فراوان است که تاکنون برای آن ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده است و به احتمال زیاد در آینده نیز یافت نخواهد شد.این که راه حل سریعی برای آن ها وجود ندارد هم اثبات شده است.البته ثابت شده است که اگر فقط برای یکی از این مساله ها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیه یبقیهٔ مساله ها خواهد شد.البته احتمال پیدا شدن چنین الگوریتمی ضعیف است.منظور از راه حل سریع آن است که زمان اجرای آن با اندازه یاندازهٔ ورودی مساله به صورت [[چندجمله ای]] رابطه داشته باشد.

== ریشه یریشهٔ انگلیسی ==

* حل نشدنی درزمان چندجمله ای بر حسب اندازه یاندازهٔ ورودی مساله ( زمان معقول)

== مفهوم و مقایسه یمقایسهٔ آن با ان پی-کامل ==

مساله یمسالهٔ H '''ان پی-سخت''' است اگر و فقط اگر مساله یمسالهٔ L از نوع [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] موجود باشد ٫ به طوری که زمان حل آن بر حسب [[چندجمله‌ای]] قابل کاهش به Hباشد: ( L ≤ _TH )به عبارتی دیگر L را میتوان در زمان زیاد با ماشین [[ویکی‌پدیا:oracle|اوراکل]] H حل کرد.به طور غیررسمی ما میتوانیم به الگوریتمی فکر کنیم که میتواندزیرروالی را برای حل H فراخوانی کند و L را در زمان زیاد حل کند اگر فراخوانی آن زیر روال فقط یک گام برای محاسبه طول بکشد.

* مساله یمسالهٔ H حداقل به سختی مسالهٔ L است. چون H میتواند برای حل L استفاده شود.

* چون L [[ویکی‌پدیا:NP-compelete |ان پی-کامل]] است ٫بنابراین به سختی مسائل نوع '''ان پی '''است. مساله یمسالهٔ H حداقل به سختی مساله یمسالهٔ '''ان پی''' است.اما H نباید '''ان پی''' باشد و بنابراین نباید از نوع [[مسئله تصمیم|مسائل تصمیم گیری]] باشد(حتی اگر از نوع مسایل تصمیم گیری باشد نیازی ندارد ازنوع مسائل '''ان پی''' باشد.)

همه یهمهٔ مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با کاهش H میتوانند در زمان زیاد حل شوند.بنابراین همه یهمهٔ مسائل در '''ان پی''' قابل کاهش به H هستند.توجه داشته باشید هر چند این شامل ترکیب کردن ۲ تبدیل است:

* اگر یک [[الگوریتم]] چندجمله‌ای برای هر مساله یمسالهٔ ان پی-سخت موجود باشد٫ سپس [[الگوریتم|الگوریتم‌]]های چندجمله‌ای برای همه یهمهٔ مسائل در '''ان پی '''وجود دارند و بنابراین [[P = NP]]

* اگر [[ویکی‌پدیا:optimization problems|مسائل بهینه سازی]] ٫H یک نسخه ینسخهٔ تصمیم گیری [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] داشته باشند٫ H یک ان پی-سخت است.

* یک اشتباه رایج این است که فکر میکنیم '''ان پی''' در ان پی-سخت بر پایه یپایهٔ غیر چند جمله‌ای است. اگر چه به طور گسترده انتظار میرود که هیچ الگوریتم غیر چند جمله‌ای بر حسب تابع زمانی برای مسائل ان پی- سخت وجود ندارد ولی این موضوع هنوز اثبات نشده‌است. علاوه بر این مسائل از نوع '''ان پی''' همچنین شامل همه یهمهٔ مسائلی هستند که میتوانند در چندجمله‌ای از [[تابع]] زمان حل شوند.

روش های مختلفی برای حل سریع ولی نزدیک به بهینه برای یک مساله یمسالهٔ ان پی-سخت وجود دارد:

* '''راه حل تقریبی قابل اثبات'''( '''[[الگوریتم‌های تقریبی]]''' ):که در آن یک الگوریتم سریع برای حل مساله ارائه میشود ولی اثبات میشود که اندازه یاندازهٔ خروجی ضریبی از اندازه یاندازهٔ خروجی بهینه یبهینهٔ مساله است.