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