ان پی سخت

مجموعهٔ «ان پی - سخت» ( به انگلیسی: NP - hard ) شامل چندهزار مسئلهٔ مختلف با کاربردهای فراوان است که تاکنون برای آن ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده است و به احتمال زیاد در آینده نیز یافت نخواهد شد. این که راه حل سریعی برای آن ها وجود ندارد هم اثبات نشده است. البته ثابت شده است که اگر فقط برای یکی از این مسئله ها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیهٔ مسئله ها خواهد شد. البته احتمال پیدا شدن چنین الگوریتمی ضعیف است. منظور از راه حل سریع آن است که زمان اجرای آن با اندازهٔ ورودی مسئله به صورت چندجمله ای رابطه داشته باشد.
ان پی سخت ( زمان چندجمله ای غیر قطعی سخت ) در نظریه پیچیدگی محاسباتی یک کلاسی از مسائل است که "دست کم به سختی سخت ترین مسئله های NP" است. مسئلهٔ H یک مسئلهٔ ان پی سخت است اگر و فقط اگر یک مسئلهٔ ان پی کامل L که زمان چندجمله ای تورینگ تقلیل ( polynomial time Turing - reducible ) به سمت H وجود داشته باشد ( L ≤ TH ) . به عبارت دیگر L می تواند در زمان چندجمله ای به وسیلهٔ دستگاه اوراکل با اوراکل H حل شود. به صورت غیررسمی می توانیم الگوریتمی در نظر بگیریم که می تواند مانند یک ماشین اوراکل به عنوان یک زیر روال برای حل H تماس بگیرد و L را در زمان چندجمله ای حل کند اگر فراخوانی زیرروال تنها یک گام برای محاسبه بگیرد. مسئلهٔ ان پی سخت می تواند به هر صورتی باشد: مسئله های تصمیم گیری، مسئله های جستجو یا مسئله های بهینه سازی. .
تعریف جایگزین ان پی سخت اغلب استفاده محدود ان پی سخت برای مسائل تصمیم گیری و سپس برای استفاده کاهش زمان چند جمله ای به چند به یک کاهش تورینگ است؛ بنابراین، زبان L ان پی سخت است اگر ∀L' ∈ NP, L' ≤ L. اگر همچنین این حالت که L در ان پی باشد بنابراین L ان پی کامل نامیده می شود.
ان پی - سخت: Non - deterministic Polynomial - time hard ) →NP - hard )
• حل نشدنی در زمان چندجمله ای بر حسب اندازهٔ ورودی مسئله ( زمان معقول )
سیستم نام گذاری خانواده ان پی گیج کننده است: مسائل ان پی سخت همه ان پی نیستند با وجود این که پسوند NP را در کلاس اسمی خود دارند. اگرچه نام هم اکنون در حال تثبیت است و بعید است تغییر کند. از طرف دیگر سیستم نام گذاری ان پی معنی عمیق تری دارد زیرا خانواده ان پی در ارتباط با کلاس ان پی تعریف شده اند:
• ان پی سخت: حداقل به سختی سخت ترین مسائل در ان پی است. برخی مثال ها نیاز ندارند ان پی باشند، در واقع آن ها حتی ممکن است مسائل تصمیم گیری نباشند.
• ان پی کامل: این ها سخت ترین مسائل در ان پی هستند. مثل مسئله ای که ان پی سخت، در ان پی است.
• ان پی آسان: حداکثر به سختی ان پی است اما لزوماً ان پی نیست. از آنجایی که آن ها ممکن است مسئله های تصمیم گیری نباشند.
• ان پی معادل: دقیقاً به سختی سخت ترین مسائل در ان پی است اما لزوماً ان پی نیست.