«نظریه‌ي پيچيدگي محاسباتي» بخشی از «نظریه‌ی محاسباتی» است که با «منابع» مورد نیاز برای حل یک مسأله سروکار دارد. عمومي‌ترين «منابع زمان» (زمان لازم براي حل کردن مسأله) و «فضا» (حافظه‌ي مورد نياز) مي‌باشند. ساير منابع مي‌تواند تعداد «پروسسور‌هاي موازي» (در حالت پردازش موازي) و ... باشند. بايد به اين نکته توجه داشت که «نظریه‌ي پيچيدگي» با «نظریه‌ي قابل حل بودن» متفاوت مي‌باشد. اين نظریه در مورد قابل حل بودن يک مسأله - بدون توجه به منابع مورد نياز آن - بحث مي‌کند. بعد از اين نظریه که بيان مي‌کند کدام مسائل قابل حل مي‌باشند و کدام مسائل غيرقابل حل، اين سؤال به‌نظر طبيعي مي‌رسد که «درجه‌ي سختي» مسأله چقدر است. «نظریه‌ي پيچيدگي محاسباتي» در اين زمينه مي‌باشد.برای سادگی کار، مسأله‌ها به کلاس‌هایی تقسیم می‌شوند به‌طوری که مسأله‌های یک کلاس از حیث «زمان» یا «فضای» مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح «کلاس‌های پیچیدگی» خوانده می‌شوند. بعضی منابع دیگری که در این نظریه بررسی مي شوند - مثل عدم تعین - صرفاً جنبه‌ی صوری دارند ولی بررسی آن‌ها موجب درک عمیق‌تر «منابع واقعی» مثل: «زمان» و «فضا» می‌شود. معروف‌ترین کلاس‌های پیچیدگی، P و NP هستند که مسأله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به‌طور شهودی می‌توان گفت P کلاس مسأله‌هایی است که الگوریتم‌هایي سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما NP شامل آن دسته از مسأله‌هاست که اگرچه ممکن است پیدا کردن جواب برای آن‌ها نیاز به «زمان زیادی» داشته باشد اما «چک کردن درستی» جواب به‌وسیله‌ي یک «الگوریتم سریع» ممکن است. البته کلاس‌هاي پيچيدگي به‌مرتبه‌ي سخت‌تري از NP نيز وجود دارند: - PSPACE مسائلي که با اختصاص دادن مقدار کافي حافظه (که اين مقدار حافظه معمولاً تابعي از اندازه‌ي مسأله است) «بدون در نظر گرفتن زمان» مورد نياز به حل آن، مي‌توانند حل شوند. - EXPTIME مسائلي که زمان مورد نياز براي حل آن‌ها به‌صورت تواني مي‌باشد. مسائل اين کلاس بسيار جذاب و سرگرم کننده مي‌باشند (حداقل براي ما!) و همه‌ي مسائل سه کلاس بالايي را نيز دربرمي‌گيرند. نکته‌ي جالب و قابل‌توجه اين است که حتي اين کلاس نيز «جامع» نمي‌باشد. يعني مسائلي وجود دارند که بهترين و کارامدترين الگوريتم‌ها نيز زمان بيش‌تري نسبت به زمان تواني مي‌گيرند. - Un-decidable يا غيرقابل تصميم‌گيري براي برخي از مسائل مي‌توانيم اثبات کنيم که الگوريتمي را نمي‌توان پيدا کردن که هميشه آن مسأله را حل مي‌کند، بدون در نظر گرفتن فضا و زمان. در اين زمينه «ريچارد ليپتون» (از صاحب‌نظران اين زمينه) در مقاله‌اي چنين مرقوم كرده است: «يک روش اثبات غيررسمي براي اين مسأله مي‌تواند اين باشد: تعداد زيادي مسأله، مثلاً به زيادي اعداد حقيقي وجود دارند، ولي تعداد برنامه‌هايي که مسائل را حل مي‌کنند در حد اعداد صحيح مي‌باشند. اما ما هميشه مي‌توانيم مسائل به‌درد بخوري را پيدا کنيم که قابل‌حل نمي‌باشند». اين سؤال که آيا مسائل کلاس P دقيقاً همان مسائل کلاس NP هستند، يکي از مهم‌ترين سؤال‌هاي بدون جواب علوم کامپيوتري مي‌باشد. به بياني ديگر اگر هميشه به اين سادگي باشد که بتوان صحت يک راه‌حل را بررسي کرد آيا پيدا کردن راه‌حل نيز مي‌تواند به آن سادگي باشد؟ براي اين سؤال يک جايزه‌ي يك ميليون دلاري از طرف «انسیتیتو ریاضی كلي» (Clay) در نظر گرفته شده است. ما هيچ دليلي براي قبول کردن آن نداريم ولي بين نظريه‌پردازان نيز اين باور وجود دارد که بايد جواب اين سؤال منفي باشد. هم‌چنين دليلي براي رد کردن آن نيز وجود ندارد.
با عرض سلام و خسته نباشید (به‌مناسبت پایان امتحانات!!) به کاربران گرامی! دوستان عزیز، شما می‌توانید در قسمت زنگ تفریح با ارائه‌ي نظرات خود و پیشنهاد موضوع‌هاي جدید و جالب برای قسمت زنگ تفریح، در قسمت «نظر شما»، ضمن مشارکت در فعالیت‌های رشد ما را در این بخش یاری کنید. منتظر نظرات شما هستیم! پیشاپیش از همکاری صمیمانه‌ی شما سپاسگذاریم! موفق باشید! |
|