نظریه پیچیدگی محاسباتی

نظریهٔ پیچیدگی رایانشی[ ۱] یا نظریهٔ پیچیدگی محاسباتی ( Computational complexity theory ) شاخه ای از نظریهٔ محاسبات، علوم نظری رایانه و ریاضی است که به بررسی دشواری حل مسائل به وسیلهٔ رایانه ( به عبارت دقیق تر به صورت الگوریتمی ) می پردازد. این نظریه بخشی از نظریهٔ رایانش است که با منابع مورد نیاز برای حل یک مسئله سروکار دارد.
عمومی ترین منابع، زمان ( مقدار زمان مورد نیاز برای حل مسئله ) و فضا ( مقدار حافظه مورد نیاز ) می باشند. از سایر منابع می تواند به تعداد پردازنده های موازی ( در حالت پردازش موازی ) و… اشاره کرد. اما در اینجا عوامل بالا مورد بحث نیستند. باید به این نکته توجه داشت که نظریه پیچیدگی با نظریه قابل حل بودن متفاوت است. این نظریه در مورد قابل حل بودن یک مسئله بدون توجه به منابع مورد نیاز آن، بحث می کند. مواردی هست که می دانیم یک مسئله جواب دارد ولی راه حل و روش حل آن هنوز ارائه نگردیده و گاهی علاوه بر مشکل مذکور حتی با در دست داشتن راه حل، منابع و ابزار لازم جهت پیاده سازی آن مسئله را نداریم.
بعد از این نظریه که بیان می کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سؤال به نظر طبیعی می رسد که درجه سختی مسئله چقدر است. نظریه پیچیدگی محاسبات در این زمینه است.
برای سادگی کار مسئله ها به کلاس هایی تقسیم می شوند، طوری که مسئله های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس ها در اصطلاح کلاس های پیچیدگی خوانده می شوند.
بعضی منابع دیگری که در این نظریه مورد بررسی قرار می گیرند، مثل عدم تعین صرفاً جنبهٔ آموزشی دارند ولی بررسی آن ها موجب درک عمیق تر منابع واقعی مثل زمان و فضا می شود.
معروف ترین کلاس های پیچیدگی، P و NP هستند که مسئله ها را از نظر زمان مورد نیاز تقسیم بندی می کنند. به طور شهودی می توان گفت P کلاس مسئله هایی است که الگوریتم های سریع برای پیدا کردن جواب آن ها وجود دارد. اما NP شامل آن دسته از مسئله هاست که اگرچه ممکن است پیدا کردن جواب برای آن ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیلهٔ یک الگوریتم سریع ممکن است. البته کلاس های پیچیدگی به مراتب سخت تری از NP نیز وجود دارند.
• P - SPACE: مسائلی که با اختصاص دادن مقدار کافی حافظه ( که این مقدار حافظه معمولاً تابعی از اندازه مسئله می باشد ) بدون در نظر گرفتن زمان مورد نیاز به حل آن، می توانند حل شوند.
• EXP - TIME: مسائلی که زمان مورد نیاز برای حل آن ها به صورت توانی می باشد. مسائل این کلاس شامل همه مسائل سه کلاس بالایی نیز می باشد. نکته جالب و قابل توجه این است که حتی این کلاس نیز جامع نمی باشد؛ یعنی مسائلی وجود دارند که بهترین و کارامدترین الگوریتم ها نیز زمان بیش تری نسبت به زمان توانی می گیرند.
• Un - decidable یا غیرقابل تصمیم گیری: برای برخی از مسائل می توانیم اثبات کنیم که الگوریتمی را نمی شود پیدا کرد که همیشه آن مسئله را حل می کند، بدون در نظر گرفتن فضا و زمان. به عقیده ریچارد لیپتون ( از صاحب نظران این زمینه ) : یک روش اثبات غیررسمی برای این مسئله می تواند این باشد: تعداد زیادی مسئله، مثلاً به زیادی اعداد حقیقی وجود دارند، ولی تعداد برنامه هایی که مسائل را حل می کنند در حد اعداد صحیح هستند. اما ما همیشه می توانیم مسائل کاربردی و مهمی را پیدا کنیم که قابل حل نیستند.