پیچیدگی محاسباتی
از ویکی‌پدیا، دانشنامهٔ آزاد.
نظریه‌ی پیچیدگی محاسباتی شاخه‌ای از علوم کامپیوتر و ریاضی است که به بررسی دشواری حل مسائل به وسیله‌ی رایانه (به عبارت دقیق‌تر به صورت الگوریتمی) می‌پردازد. این نظریه بخشی از نظریه‌ی محاسباتی است که با منابع مورد نیاز برای حل یک مساله سروکار دارد. عمومي‌ترين منابع زمان (چقدر زمان براي حل کردن مساله لازم است) و فضا (چقدر حافظه مورد نياز است) مي‌باشند. ساير منابع مي‌تواند تعداد پروسسور‌هاي موازي (در حالت پردازش موازي) و ... باشند. اما در اين مقاله ما در مورد عواملي مثل عوامل بالا بحثي نکرده‌ايم. بايد به اين نکته توجه داشت که نظریه پيچيدگي با نظریه قابل حل بودن متفاوت مي‌باشد. اين نظریه در مورد قابل حل بودن يک مساله بدون توجه به منابع مورد نياز آن، بحث مي‌کند. بعد از اين نظریه که بيان مي‌کند کدام مسائل قابل حل مي‌باشند و کدام مسائل غيرقابل حل، اين سوال به نظر طبيعي مي‌رسد که درجه سختي مساله چقدر است. نظریه پيچيدگي محاسبات در اين زمينه مي‌باشد.
برای سادگی کار مساله‌ها به کلاس‌هایی تقسیم می‌شوند به طوری که مساله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح کلاس‌های پیچیدگی خوانده می‌شوند.
بعضی منابع دیگری که در این نظریه مورد بررسی قرار می‌گیرند، مثل عدم تعین صرفا جنبه‌ی صوری دارند ولی بررسی آنها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.
معروف‌ترین کلاس‌های پیچیدگی، P و NP هستند که مساله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت P کلاس مساله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آنها وجود دارد. اما NP شامل آن دسته از مساله‌هاست که اگرچه ممکن است پیدا کردن جواب برای آنها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیله‌ٔ یک الگوریتم سریع ممکن است. البته کلاس‌هاي پيچيدگي به مرتبه سخت‌تري از NP نيز وجود دارند.
- PSPACE: مسائلي که با اختصاص دادن مقدار کافي حافظه (که اين مقدار حافظه معمولا تابعي از اندازه مساله مي‌باشد) بدون در نظر گرفتن زمان مورد نياز به حل آن، مي‌توانند حل شوند.
- EXPTIME: مسائلي که زمان مورد نياز براي حل آنها به صورت تواني مي‌باشد. مسائل اين کلاس بسيار جذاب و سرگرم کننده مي‌باشند (حداقل براي ما!). و شامل همه مسائل سه کلاس بالايي نيز مي‌باشد. نکته جالب و قابل توجه اين مي‌باشد که حتي اين کلاس نيز جامع نمي‌باشد. يعني مسائلي وجود دارند که بهترين و کارامدترين الگوريتم‌ها نيز زمان بيشتري نسبت به زمان تواني مي‌گيرند.
- Un-decidable يا غيرقابل تصميم‌گيري: براي برخي از مسائل مي‌توانيم اثبات کنيم که الگوريتمي را نمي‌شود پيدا کردن که هميشه آن مساله را حل مي‌کند، بدون در نظر گرفتن فضا و زمان. در اين زمينه آقاي ريچارد ليپتون (از صاحب‌نظران اين زمينه) در مقاله‌اي نوشته‌اند: يک روش اثبات غيررسمي براي اين مساله مي‌تواند اين باشد: تعداد زيادي مساله، مثلا به زيادي اعداد حقيقي وجود دارند، ولي تعداد برنامه‌هايي که مسائل را حال مي‌کنند در حد اعداد صحيح مي‌باشند. اما ما هميشه مي‌توانيم مسائل به دردبخوري را پيدا کنيم که قابل حل نمي‌باشند.
فهرست مندرجات |
[ویرایش] آيا P=NP مي‌باشد؟
اين سوال که آيا مسائل کلاس P دقيقا همان مسائل کلاس NP مي باشند، يکي از مهم ترين سوال‌هاي بدون جواب علوم کامپيوتري مي‌باشد. به بياني ديگر اگر هميشه به اين سادگي باشد که بتوان صحت يک راه‌حل را بررسي کرد، آيا پيدا کردن راه‌حل نيز مي‌تواند به آن سادگي باشد؟ براي اين سوال يک جايزه 1 ميليون دلاري از طرف انسیتیتو ریاضی Clay در نظرگرفته شده‌است. ما هيچ دليلي براي قبول کردن آن نداريم ولي بين نظريه‌پردازان نيز اين باور وجود دارد که بايد جواب اين سوال منفي باشد. همچنين دليلي براي رد کردن آن نيز وجود ندارد.
[ویرایش] پیچیدگی زمانی
پيچيدگي زماني يک مساله تعداد گام‌هاي مورد نياز براي حل يک نمونه از يک مساله به عنوان تابعي از اندازه‌ي ورودي (معمولا بوسيله تعداد بيت‌ها بيان مي‌شود) بوسيله کارآمدترين الگوريتم مي‌باشد. براي درک بهتر اين مساله، فرض کنيد که يک مساله با ورودي n بيت در n² گام حل شود. در اين مثال مي‌گوييم که مساله از درجه پيچيدگي n² مي‌باشد. البته تعداد دقيق گام‌ها بستگي به ماشين و زبان مورد استفاده دارد. اما براي صرف نظر کردن از اين مشکل، نشانه‌گذاری O بزرگ (Big O notation) معمولا بکار مي‌رود. اگر يک مساله پيچيدگي زماني از مرتبه (O(n² روي يک کامپيوتر نمونه داشته باشد، معمولا روي اکثر کامپيوتر‌هاي ديگر نيز پيچيدگي زماني از مرتبه (O(n² خواهد‌داشت. پس اين نشانه به ما کمک مي‌کند که صرف نظر از يک کامپيوتر خاص، يک حالت کلي براي پيچيدگي زماني يک الگوريتم ارائه دهيم.
[ویرایش] معرفي NP-Complete
تا اين بخش از مقاله مسائلي معرفي شدند که اگر بتوان روشي براي حل آنها حدس زد، در زمان نزديک به زمان خطي و يا حداقل در زمان چند جمله‌اي برحسب ورودي مي‌توانستيم صحت راه‌حل را بررسي کنيم. ولي NP-Completeها مسائلي هستند که اثبات شده به سرعت قابل حل نيستند. در تئوري پيچيدگي NP-Completeها دشوارترين مسائل کلاس NP هستند و جزء مسائلي مي‌باشند که احتمال حضورشان در کلاس P خيلي کم است. علت اين امر اين مي‌باشد که اگر يک راه‌حل پيدا شود که بتوانديک مساله NP-Complete را حل کند، مي‌توان از آن الگوريتم براي حل کردن سريع همه مسائل NP-Complete استفاده کرد. به خاطر اين مساله و نيز بخاطر اينکه تحقيقات زيادي براي پيدا کردن الگوريتم کارآمدي براي حل کردن اينگونه مسائل با شکست مواجه شده‌اند، وقتي که مساله‌اي به عنوان NP-Complete معرفي شد، معمولا اينطور قلمداد مي‌شود که اين مساله در زمان Polynomial قابل حل شدن نمي‌باشد، يا به بياني ديگر هيچ الگوريتمي وجود ندارد که اين مساله را در زمان Polynomial حل نمايد. کلاس متشکل از مسائل NP-Compete با نام NP-C نيز خوانده مي‌شود.
[ویرایش] بررسي ناکارآمد بودن زماني
مسائلي که در تئوري قابل حل شدن مي‌باشند ولي در عمل نمي‌توان آنها را حل کرد، محال يا ناشدني مي‌نامند. در حالت کلي فقط مسائلي که زمان آنها به صورت Polynomial مي‌باشد و اندازه ورودي آنها در حد کوچک يا متوسط مي‌باشد قابل حل شدن مي‌باشند. مسائلي که زمان آنها به صورت تواني (EXPTIME-complete) مي‌باشند به عنوان مسائل محال يا ناشدني شناخته شده‌اند. همچنين اگر مسائل رده NP جز مسائل رده P نباشند، مسائل NP-Complete نيز به عنوان محال يا نشدني خواهند بود. براي ملموس‌تر شدن اين مساله فرض کنيد که يک مساله 2n مرحله لازم دارد تا حل شود (n اندازه ورودي مي‌باشد). براي مقادير کوچک n=100 و با در نظر گرفتن کامپيوتري که 1010 (10 giga) عمليات را در يک ثانيه انجام مي‌دهد، حل کردن اين مساله زماني حدود 1012 * 4 سال طول خواهد کشيد، که اين زمان از عمر فعلي جهان بيشتر است!
[ویرایش] چرا حل مسائل NP-Complete مشکل است؟
به خاطر اينکه مسائل بسيار مهمي در اين کلاس وجود دارد، تلاش‌هاي بسيار زيادي صورت گرفته است تا الگوريتم‌هايي براي حل مسائل NP که زمان آن به صورت Polynomial از اندازه ورودي باشد، پيدا شود. باوجود اين، مسائل خيلي بيشتري در اين رده وجود دارد که زمان لازم براي حل آنها به صورت Super-Polynomial مي‌باشد. اين مساله که آيا اين مسائل در زمان Polynomial قابل حل شدن مي‌باشند، يکي از مهم‌ترين چالش‌هاي علوم کامپيوتري مي‌باشد.
[ویرایش] روش‌هايي براي حل مسائل NP-Complete
به خاطر اينکه تعداد مسائل NP-Complete بسيار زياد مي‌باشد، شناختن اينگونه مسائل به ما کمک مي‌کند تا دست از پيدا کردن يک الگوريتم سريع و جامع برداريم و يکي از روش‌هاي زير را امتحان کنيم:
- به کار بردن يک روش حدسي: يک الگوريتم که تا حد قابل قبولي در بيشتر موارد درست کار مي‌کند، ولي تضميني وجود ندارد که در همه موارد با سرعت قابل قبول نتيجه درستي توليد کند.
- حل کردن تقريبي مساله به جاي حل کردن دقيق آن: اغلب موارد اين روش قابل قبول مي‌باشد که با يک الگوريتم نسبتا سريع يک مساله را به طور تقريبي حل کنيم که مي‌توان ثابت کرد جواب بدست آمده تقرييا نزديک به جواب کاملا صحيح مي‌باشد.
- الگوريتم‌هاي زمان تواني را به کار ببريم: اگر واقعا مجبور به حل کردن مساله به طور کامل هستيم، مي‌توان يک الگوريتم با زمان تواني نوشت و ديگر نگران پيدا کردن جواب بهتر نباشيم.
- از خلاصه کردن استفاده کنيم: خلاصه کردن به اين مفهوم مي‌باشد که از برخي اطلاعات غيرضروري مي‌توان صرف نظر کرد. اغلب اين اطلاعات براي پياده‌سازي مساله پيچيده در دنياي واقعي مورد نياز مي‌باشد، ولي در شرايطي که بخواهيم به نحوي مساله را حل کنيم (حداقل به صورت تئوري و نه در عمل) مي‌توان از برخي اطلاعات غيرضروري صرف نظر کرد.
[ویرایش] نمونه مساله
يک مسير ساده در يک گراف به مسيري اطلاق مي‌شود که هيچ راس يا يال تکراري در آن وجود‌نداشته‌باشد. براي پياده سازي مساله ما به اين احتياج داريم که بتوانيم يک سوال بلي/خير طراحي کنيم. با داشتن گراف G، رئوس s و t و عدد k آيا يک مسير ساده از s به t با حداقل k يال وجوددارد؟ راه‌حل اين مساله جواب سوال خواهد بود. چرا اين مساله NP مي‌باشد؟ چون اگر مسيري به شما داده شود، به راحتي مي‌توان طول مسير را مشخص نمود و آن را با k مقايسه کرد. همه اين کار‌ها در زمان خطي و صد البته در زمان Polynomial قابل انجام مي‌باشد. اگر چه مي نمي‌دانيم که اين مساله آيا در کلاس P مي‌باشد يا نه، با اين حال روش خاصي براي پيدا کردن مسيري با ويژگي‌هاي ذکر شده نيز وجود بيان نشده است. و در حقيقت اين مساله جز NP-Completeها مي‌باشد، پس مي‌توان به اين نتيجه نيز رسيد که الگوريتمي کارآمد با چنان عمليات وجود ندارد. الگوريتم‌هايي وجود دارند که اين مساله را حل مي‌کنند، به عنوان مثال همه مسير‌هاي موجود و ممکن را بررسي نموده و نتايج مقايسه شوند که آيا اين مسير مساله را حل مي‌کند يا نه. اما تا آنجايي که مي‌دانيم، الگوريتمي با زمان Polynomial براي حل اين مساله وجود ندارد.
منابع:
- M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of P-Completeness. New York: W. H. Freeman، 1983، ISBN 0716710455.
