مسئله بهینه‌سازی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
|||
خط ۳۲:
*زبان های <math>\scriptstyle \{\,x\,\mid\, x \in I \,\}</math> و <math>\scriptstyle \{\,(x,y)\, \mid\, y \in f(x) \,\}</math> می توانند در زمان چند جمله ای مشخص شوند و
*m در زمان چندجمله ای قابل محاسبه است.
این دلالت بر این دارد که مسأله تصمیم متناظر، یک NP است. در علوم کامپیوتر، معمولاً مسائل بهینه سازی جالب توجه، ویژگی های بالا را دارند و بنابراین مسائل NPO هستند. یک مسأله به علاوه یک مسأله بهینه سازی نوع P یا PO خوانده می شود اگر
NPOPB یک دسته دیگر است؛ NPO با تابع هزینه محدود به چندجمله ای. مسائلی با این شرایط، ویژگی های مطلوب زیادی دارند.
| |||