مسئله محاسباتی انجام‌پذیر

یک مسئله محاسباتی انجام‌پذیر نامیده می‌شود اگر الگوریتم کارایی برای حل آن وجود داشته باشد. توضیح آنکه الگوریتمی کارا است که پیچیدگی آن به وسیله یک چند جمله‌ای از درجه $n$ کراندار شده باشد.

یک مسئله محاسباتی انجام‌ناپذیر خواهد بود اگر ثابت بشود الگوزیتمی کارا برای حل آن وجود ندارد.

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

جستارهای وابسته

• پیچیدگی (الگوریتم)
• متوسط پیچیدگی (الگوریتم)

منابع

• چارتراند- اولرمن (۱۳۸۳)، نظریه الگوریتمی و کاربردی گرافها، ترجمهٔ دکتر مهدی تشکری هاشمی، دانشگاه صنعتی امیرکبیر، ص. ۵۲