ان‌پی سخت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
←مفهوم و مقایسهٔ آن با ان پی-کامل: کاما فارسی، است نه , برچسب‌ها: ویرایش همراه ویرایش از وبگاه همراه |
FreshmanBot (بحث | مشارکت‌ها) جز ←مفهوم و مقایسهٔ آن با ان پی-کامل: اصلاح فاصله مجازی + اصلاح نویسه با ویرایشگر خودکار فارسی |
||
خط ۷:
* حل نشدنی در زمان چندجمله‌ای بر حسب اندازهٔ ورودی مسئله (زمان معقول)
== مفهوم و مقایسهٔ آن با ان پی-کامل ==
مسئلهٔ H '''ان پی-سخت''' است اگر و فقط اگر مسئلهٔ L از نوع [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] موجود
مسائل ان پی-سخت ممکن است از هر نوعی باشند:[[مسئله تصمیم|مسائل تصمیم گیری]]٫[[ویکی‌پدیا:search problems|مسائل جستجو]]٫[[ویکی‌پدیا:optimization problems|مسائل بهینه سازی]].
طبق روال تعریف: (توجه داشته باشید که
* مسئلهٔ H حداقل به سختی مسئلهٔ L است. چون H می‌تواند برای حل L استفاده شود.
* چون L [[ویکی‌پدیا:NP-compelete|ان پی-کامل]] است ٫بنابراین به سختی مسائل نوع '''ان پی '''است. مسئلهٔ H حداقل به سختی مسئلهٔ '''ان پی''' است.اما H نباید '''ان پی''' باشد و بنابراین نباید از نوع [[مسئله تصمیم|مسائل تصمیم گیری]] باشد(حتی اگر از نوع مسایل تصمیم‌گیری باشد نیازی ندارد ازنوع مسائل '''ان پی''' باشد.)
| |||