ان‌پی سخت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات :جایگزینی پیوند قرمز با مترادف فارسی np-complete > ان‌پی کامل |
جز ربات :جایگزینی پیوند قرمز با مترادف فارسی P = NP > مسئله برابری پی و ان‌پی |
||
خط ۱۷:
# از L به H با کاهش چند جمله‌ای [[ماشین تورینگ|تورینگ]]. [http://fa.wikipedia.org/wiki/%D9%85%D8%A7%D8%B4%DB%8C%D9%86_%D8%AA%D9%88%D8%B1%DB%8C%D9%86%DA%AF]
* اگر یک [[الگوریتم]] چندجمله‌ای برای هر مسالهٔ ان پی-سخت موجود باشد٫ سپس [[الگوریتم|الگوریتم]]های چندجمله‌ای برای همهٔ مسائل در '''ان پی '''وجود دارند و بنابراین [[
* اگر P ≠ NP باشد ٫ مسائل ان پی-سخت راه حلی در زمان‌های زیاد ندارند.زمانی که [[
* اگر [[ویکی‌پدیا:optimization problems|مسائل بهینه سازی]] ٫H یک نسخهٔ تصمیم گیری [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] داشته باشند٫ H یک ان پی-سخت است.
* یک اشتباه رایج این است که فکر میکنیم '''ان پی''' در ان پی-سخت بر پایهٔ غیر چند جمله‌ای است. اگر چه به طور گسترده انتظار میرود که هیچ الگوریتم غیر چند جمله‌ای بر حسب تابع زمانی برای مسائل ان پی- سخت وجود ندارد ولی این موضوع هنوز اثبات نشده‌است. علاوه بر این مسائل از نوع '''ان پی''' همچنین شامل همهٔ مسائلی هستند که میتوانند در چندجمله‌ای از [[تابع]] زمان حل شوند.
| |||