ان‌پی سخت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
مشکل نگارشی وجود داشت؛ آن را برطرف کردم. |
FreshmanBot (بحث | مشارکت‌ها) جز اصلاح فاصله مجازی + اصلاح نویسه با ویرایشگر خودکار فارسی |
||
خط ۵:
== ریشهٔ انگلیسی ==
'''ان پی-سخت:''' [[ویکی‌پدیا:NP (complexity)|Non-deterministic Polynomial-time]] hard)→[[ویکی‌پدیا:NP-hard|NP-hard]])
* حل نشدنی
== مفهوم و مقایسهٔ آن با ان پی-کامل ==
مسئلهٔ H '''ان پی-سخت''' است اگر و فقط اگر مسئلهٔ L از نوع [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] موجود باشد ٫ به‌طوری‌که زمان حل آن بر حسب [[چندجمله‌ای]] قابل کاهش به Hباشد: (L ≤ <sub>T</sub>H)به عبارتی دیگر L را
مسائل ان پی-سخت ممکن است از هر نوعی باشند:[[مسئله تصمیم|مسائل تصمیم گیری]]٫[[ویکی‌پدیا:search problems|مسائل جستجو]]٫[[ویکی‌پدیا:optimization problems|مسائل بهینه سازی]].
طبق روال تعریف: (توجه داشته باشید که اینها صرفاً ادعا هستند نه تعریف):
خط ۱۳:
* چون L [[ویکی‌پدیا:NP-compelete|ان پی-کامل]] است ٫بنابراین به سختی مسائل نوع '''ان پی '''است. مسئلهٔ H حداقل به سختی مسئلهٔ '''ان پی''' است.اما H نباید '''ان پی''' باشد و بنابراین نباید از نوع [[مسئله تصمیم|مسائل تصمیم گیری]] باشد(حتی اگر از نوع مسایل تصمیم‌گیری باشد نیازی ندارد ازنوع مسائل '''ان پی''' باشد.)
* مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با زمان زیاد با ۱ واحد کاهش به یکدیگر تبدیل می‌شوند(همچنین تحولات چند جمله‌ای نیز نامیده می‌شوند.)
همهٔ مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با کاهش H
# از [[ویکی‌پدیا:NP-complete|'''ان پی-کامل:''']][[مسئله تصمیم|مسائل تصمیم گیری]] به مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با تحولات چندجمله‌ای
# از L به H با کاهش چند جمله‌ای [[ماشین تورینگ|تورینگ]]. [[ماشین_تورینگ]]
خط ۱۹:
* اگر P ≠ NP باشد ٫ مسائل ان پی-سخت راه حلی در زمان‌های زیاد ندارند.زمانی که [[مسئله برابری پی و ان‌پی]] باشد ٫ مسائل حل نمی‌شوند.حتی اگر مسائل ان پی-سخت بتوانند در زمان زیاد حل شوند.
* اگر [[ویکی‌پدیا:optimization problems|مسائل بهینه سازی]] ٫H یک نسخهٔ تصمیم‌گیری [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] داشته باشند٫ H یک ان پی-سخت است.
* یک اشتباه رایج این است که فکر می‌کنیم '''ان پی''' در ان پی-سخت بر پایهٔ غیر چند جمله‌ای است. اگر چه به‌طور گسترده انتظار میرود که هیچ الگوریتم غیر چند جمله‌ای بر حسب تابع زمانی برای مسائل ان پی- سخت وجود ندارد ولی این موضوع هنوز اثبات نشده‌است. علاوه بر این مسائل از نوع '''ان پی''' همچنین شامل همهٔ مسائلی هستند که
== روش حل مسایل ان پی-سخت ==
| |||