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

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

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

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

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

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

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

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

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