ان‌پی سخت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Levin~fawiki (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
Levin~fawiki (بحث | مشارکت‌ها) |
||
خط ۲۰:
*اگر مسایل بهینه سازی H,یک نسخهٔ تصمیم گیری NPکامل داشته باشند.پس Hیک NPسخت است.
*یک اشتباه رایج این است که فکر میکنیمNP در NPسخت بر پایهٔ غیر چند جمله‌ای است. اگر چه به طور گسترده انتظار میرود که هیچ الگوریتم غیر چند جمله‌ای زمان برای مسایل NP سخت وجود ندارد.این هرگز اثبات نشده‌است. علاوه بر این مسایل از نوع NP همچنین شامل همهٔ مسایلی هستند که میتوانند در چندجمله‌ای از تابع زمان حل شوند.
==روش حل مسایل ان پی-سخت==
روش های مختلفی برای حل سریع ولی نزدیک به بهینه برای یک مساله ی ان پی-سخت وجود دارد:
| |||