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

جز (ربات: حذف میان‌ویکی موجود در ویکی‌داده: ۳۴ میان‌ویکی)
== مقدمه ==
 
عمومی‌ترین منابعمنابع، زمان (چقدرمقدار زمان مورد نیاز برای حل کردن مساله لازم است) و فضا (چقدرمقدار حافظه مورد نیاز است) می‌باشند. از سایر منابع می‌تواند به تعداد پروسسورهایپردازنده های موازی (در حالت [[پردازش موازی]]) و... باشنداشاره کرد. اما در این صفحهاینجا عوامل بالا مورد بحث نیستند. باید به این نکته توجه داشت که نظریه پیچیدگی با [[نظریه قابل حل بودن]] متفاوت است. این نظریه در مورد قابل حل بودن یک مساله بدون توجه به منابع مورد نیاز آن، بحث می‌کند.مواردی هست که میدانیم فلان مسئله جواب دارد ولی راه حل و روش حل ان هنوز ارائه نگرددیدو گاهی علاوه مشکل مذکور حتی با دست داشتن راه حل منابع و ابزار کاری جهت پیاده سازی ان را نداریم
مواردی هست که میدانیم یک مسئله جواب دارد ولی راه حل و روش حل آن هنوز ارائه نگرددیده و گاهی علاوه بر مشکل مذکور حتی با در دست داشتن راه حل ، منابع و ابزار لازم جهت پیاده سازی ان مسئله را نداریم.
 
بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سوال به نظر طبیعی می‌رسد که [[درجه سختی]] مساله چقدر است. نظریه پیچیدگی محاسبات در این زمینه‌است.
 
برای سادگی کار مساله‌ها به کلاس‌هایی تقسیم می‌شوند بهمی‌شوند، طوری که مساله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح [[کلاس‌های پیچیدگی]] خوانده می‌شوند.
 
بعضی منابع دیگری که در این نظریه مورد بررسی قرار می‌گیرند، مثل [[عدم تعین]] صرفاً جنبهٔ صوریآموزشی دارند ولی بررسی آن‌ها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.
 
معروف‌ترین کلاس‌های پیچیدگی، '''P''' و '''NP''' هستند که مساله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت '''P''' کلاس مساله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما '''NP''' شامل آن دسته از مساله‌هاست که اگرچه ممکن است پیدا کردن جواب برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیله‌ٔ یک [[کارایی الگوریتم‌ها|الگوریتم سریع]] ممکن است.
البته کلاس‌های پیچیدگی به مرتبهمراتب سخت‌تری از '''NP''' نیز وجود دارند.
* '''P-SPACE''': مسائلی که با اختصاص دادن مقدار کافی حافظه (که این مقدار حافظه معمولاً تابعی از اندازه مساله می‌باشد) بدون در نظر گرفتن زمان مورد نیاز به حل آن، می‌توانند حل شوند.
* '''EXP-TIME''': مسائلی که زمان مورد نیاز برای حل آنها به صورت توانی می‌باشد. مسائل این کلاس شامل همه مسائل سه کلاس بالایی نیز می‌باشد. نکته جالب و قابل توجه این است که حتی این کلاس نیز جامع نمی‌باشد. یعنی مسائلی وجود دارند که بهترین و کارامدترین الگوریتم‌ها نیز زمان بیش‌تری نسبت به زمان توانی می‌گیرند.
* '''Un-decidable''' یا '''غیرقابل تصمیم‌گیری''': برای برخی از مسائل می‌توانیم اثبات کنیم که الگوریتمی را نمی‌شود پیدا کرد که همیشه آن مساله را حل می‌کند، بدون در نظر گرفتن فضا و زمان. در این زمینه آقای [[ریچارد لیپتون]] (از صاحب‌نظران این زمینه) در مقاله‌ای نوشته‌اند: یک روش اثبات غیررسمی برای این مساله می‌تواند این باشد: تعداد زیادی مساله، مثلاً به زیادی اعداد حقیقی وجود دارند، ولی تعداد برنامه‌هایی که مسائل را حل می‌کنند در حد اعداد صحیح هستند. اما ما همیشه می‌توانیم مسائل بهکاربردی دردبخوریو مهمی را پیدا کنیم که قابل حل نیستند.
 
== آیا P=NP است؟ ==
۱

ویرایش