پیچیدگی محاسباتی

از ویکی‌پدیا، دانشنامهٔ آزاد.

نظریهٔ پیچیدگی محاسباتی شاخه‌ای از علوم کامپیوتر و ریاضی است که به بررسی دشواری حل مسائل به وسیلهٔ رایانه (به عبارت دقیق‌تر به‌ صورت الگوریتمی) می‌پردازد.

آن چه حل یک مساله را از این منظر دشوار یا آسان می‌کند، منابعی است که برای حل مساله به آن نیازمندیم. مهم‌ترین منابع مورد بررسی عبارتند از زمان و فضای (حافظهٔ) مورد نیاز برای حل مساله.

برای سادگی کار مساله‌ها به کلاس‌هایی تقسیم می‌شوند به طوری که مساله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح کلاس‌های پیچیدگی خوانده می‌شوند.

بعضی منابع دیگری که در این نظریه مورد بررسی قرار می‌گیرند، مثل عدم تعین صرفا جنبهٔ صوری دارند ولی بررسی آن‌ها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.

معروف‌ترین کلاس‌های پیچیدگی، P و NP هستند که مساله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت P کلاس مساله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما NP شامل آن دسته از مساله‌هاست که اگرچه ممکن است پیدا کردن جواب ‌برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیله‌ٔ یک الگوریتم سریع ممکن است.

مهم‌ترین مساله‌ی حل نشده‌ی نظریهٔ پیچیدگی محاسباتی این است که آیا P و NP با هم برابرند یا نه. اکثر محققان حدس می‌زنند که جواب منفی است.

تصویر:Computer-stub.png این نوشتار دربارهٔ رایانه ناقص است. با گسترش آن به ویکی‌پدیا کمک کنید.