تفاوت میان نسخه‌های «نظریه پیچیدگی محاسباتی»

جز
 
عمومی‌ترین منابع، زمان (مقدار زمان مورد نیاز برای حل مساله) و فضا (مقدار حافظه مورد نیاز) می‌باشند. از سایر منابع می‌تواند به تعداد پردازنده های موازی (در حالت [[پردازش موازی]]) و... اشاره کرد. اما در اینجا عوامل بالا مورد بحث نیستند. باید به این نکته توجه داشت که نظریه پیچیدگی با [[نظریه قابل حل بودن]] متفاوت است. این نظریه در مورد قابل حل بودن یک مساله بدون توجه به منابع مورد نیاز آن، بحث می‌کند.
مواردی هست که میدانیم یک مسئله جواب دارد ولی راه حل و روش حل آن هنوز ارائه نگرددیدهنگردیده و گاهی علاوه بر مشکل مذکور حتی با در دست داشتن راه حل ،حل، منابع و ابزار لازم جهت پیاده سازیپیاده‌سازی انآن مسئله را نداریم.
 
بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سوال به نظر طبیعی می‌رسد که [[درجه سختی]] مساله چقدر است. نظریه پیچیدگی محاسبات در این زمینه‌است.
۱۷٬۷۰۷

ویرایش