ان‌پی سخت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Levin~fawiki (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
Levin~fawiki (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
||
خط ۳:
مجموعه ی «'''ان‌پی-سخت'''» شامل چندهزار مساله ی مختلف با کاربردهای فراوان است که تاکنون برای آن ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده است و به احتمال زیاد در آینده نیز یافت نخواهد شد.این که راه حل سریعی برای آن ها وجود ندارد هم اثبات شده است.البته ثابت شده است که اگر فقط برای یکی از این مساله ها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیه ی مساله ها خواهد شد.البته احتمال پیدا شدن چنین الگوریتمی ضعیف است.منظور از راه حل سریع آن است که زمان اجرای آن با اندازه ی ورودی مساله به صورت [[چندجمله ای]] رابطه داشته باشد.
==ریشه ی انگلیسی ==
'''ان پی-سخت:''' [[Wikipedia:NP (complexity)|Non-deterministic Polynomial-time]] hard)→[[Wikipedia:NP-hard|NP-hard]])
==مفهوم و مقایسه ی آن با ان پی-کامل==
مساله ی H '''ان پی-سخت''' است اگر و فقط اگر مساله ی L از نوع [[Wikipedia:NP-complete|'''ان پی-کامل''']] موجود باشد ٫ به طوری که زمان حل آن بر حسب [[چندجمله‌ای]] قابل کاهش به Hباشد: ( L ≤ <sub>T</sub>H )به عبارتی دیگر L را میتوان در زمان زیاد با ماشین [[Wikipedia:oracle|اوراکل]] H حل کرد.به طور غیررسمی ما میتوانیم به الگوریتمی فکر کنیم که میتواندزیرروالی را برای حل H فراخوانی کند و L را در زمان زیاد حل کند اگر فراخوانی آن زیر روال فقط یک گام برای محاسبه طول بکشد.
| |||