مسئله محاسباتی انجامپذیر
پرش به ناوبری
پرش به جستجو
یک مسئله محاسباتی انجامپذیر نامیده میشود اگر الگوریتم کارایی برای حل آن وجود داشته باشد. توضیح آنکه الگوریتمی کارا است که پیچیدگی آن به وسیله یک چند جملهای از درجه کراندار شده باشد.
یک مسئله محاسباتی انجامناپذیر خواهد بود اگر ثابت بشود الگوزیتمی کارا برای حل آن وجود ندارد.
به عنوان مثال مسئله معروف فرش کردن یک نمونه از مسائل انجامناپذیر است. برگر[۱] ثابت کردهاست برای تعیین اینکه آیا صفحه را میتوان با یک چند ضلعی مشخص فرش کرد، الگوریتمی کارا وجود ندارد.
پانویس
جستارهای وابسته
منابع
- ↑ Berger