انپی سخت
From Wikipedia, the free encyclopedia
مجموعهٔ «انپی-سخت» (به انگلیسی: NP-hard) شامل چندهزار مسئلهٔ مختلف با کاربردهای فراوان است که تاکنون برای آنها راه حل سریع و قابل انجام در زمان معقول پیدا نشدهاست و به احتمال زیاد در آینده نیز یافت نخواهد شد. این که راه حل سریعی برای آنها وجود ندارد هم اثبات نشدهاست. البته ثابت شدهاست که اگر فقط برای یکی از این مسئلهها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیهٔ مسئلهها خواهد شد. البته احتمال پیدا شدن چنین الگوریتمی ضعیف است. منظور از راه حل سریع آن است که زمان اجرای آن با اندازهٔ ورودی مسئله به صورت چندجملهای رابطه داشته باشد.
این مقاله نیازمند تمیزکاری است. لطفاً تا جای امکان آنرا از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد. |
ان پی سخت (زمان چندجملهای غیر قطعی سخت) در نظریه پیچیدگی محاسباتی یک کلاسی از مسائل است که "دست کم به سختی سختترین مسئلههای NP" است. مسئلهٔ H یک مسئلهٔ ان پی سخت است اگر و فقط اگر یک مسئلهٔ ان پی کامل L که زمان چندجملهای تورینگ تقلیل (polynomial time Turing-reducible) به سمت H وجود داشته باشد (L ≤ TH). به عبارت دیگر L میتواند در زمان چندجملهای به وسیلهٔ دستگاه اوراکل با اوراکل H حل شود. به صورت غیررسمی میتوانیم الگوریتمی در نظر بگیریم که میتواند مانند یک ماشین اوراکل به عنوان یک زیر روال برای حل H تماس بگیرد و L را در زمان چندجملهای حل کند اگر فراخوانی زیرروال تنها یک گام برای محاسبه بگیرد. مسئلهٔ ان پی سخت میتواند به هر صورتی باشد: مسئلههای تصمیمگیری، مسئلههای جستجو یا مسئلههای بهینهسازی..