ان‌پی سخت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز توضیح تصویر بندانگشتی به فارسی |
Yamaha5Bot (بحث | مشارکت‌ها) جز ←مفهوم و مقایسهٔ آن با ان پی-کامل: تمیزکاری با استفاده از AWB |
||
خط ۱۵:
همهٔ مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با کاهش H می‌توانند در زمان زیاد حل شوند. بنابراین همهٔ مسائل در '''ان پی''' قابل کاهش به H هستند. توجه داشته باشید هر چند این شامل ترکیب کردن ۲ تبدیل است:
# از [[ویکی‌پدیا:NP-complete|'''ان پی-کامل:''']][[مسئله تصمیم|مسائل تصمیم گیری]] به مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با تحولات چندجمله‌ای
# از L به H با کاهش چند جمله‌ای [[ماشین تورینگ|تورینگ]]. [[
* اگر یک [[الگوریتم]] چندجمله‌ای برای هر مسئلهٔ ان پی-سخت موجود باشد٫ سپس [[الگوریتم]]های چندجمله‌ای برای همهٔ مسائل در '''ان پی '''وجود دارند و بنابراین [[مسئله برابری پی و ان‌پی]]
* اگر P ≠ NP باشد ٫ مسائل ان پی-سخت راه حلی در زمان‌های زیاد ندارند. زمانی که [[مسئله برابری پی و ان‌پی]] باشد ٫ مسائل حل نمی‌شوند. حتی اگر مسائل ان پی-سخت بتوانند در زمان زیاد حل شوند.
| |||