موضوع مقاله: نظریه پیچیدگی محاسباتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نظریه پیچیدگی محاسباتی | مقدمه: بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سؤال به نظر طبیعی می‌رسد که درجه سختی مسئله چقدر است. | ## بخش 1: نظریه پیچیدگی محاسباتی | برای سادگی کار مسئله‌ها به کلاس‌هایی تقسیم می‌شوند، طوری که مسئله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. معروف‌ترین کلاس‌های پیچیدگی، P و NP هستند که مسئله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به‌طور شهودی می‌توان گفت P کلاس مسئله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما NP شامل آن دسته از مسئله‌هاست که اگرچه ممکن است پیدا کردن جواب برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیلهٔ یک الگوریتم سریع ممکن است. P-SPACE: مسائلی که با اختصاص دادن مقدار کافی حافظه (که این مقدار حافظه معمولاً تابعی از اندازه مسئله می‌باشد) بدون در نظر گرفتن زمان مورد نیاز به حل آن، می‌توانند حل شوند. نکته جالب و قابل توجه این است که حتی این کلاس نیز جامع نمی‌باشد؛ یعنی مسائلی وجود دارند که بهترین و کارامدترین الگوریتم‌ها نیز زمان بیش‌تری نسبت به زمان توانی می‌گیرند. Un-decidable یا غیرقابل تصمیم‌گیری: برای برخی از مسائل می‌توانیم اثبات کنیم که الگوریتمی را نمی‌شود پیدا کرد که همیشه آن مسئله را حل می‌کند، بدون در نظر گرفتن فضا و زمان. به عقیده ریچارد لیپتون (از صاحب‌نظران این زمینه): یک روش اثبات غیررسمی برای این مسئله می‌تواند این باشد: تعداد زیادی مسئله، مثلاً به زیادی اعداد حقیقی وجود دارند، ولی تعداد برنامه‌هایی که مسائل را حل می‌کنند در حد اعداد صحیح هستند. دقیقاً برابر بودن مسائل کلاس P با مسائل کلاس NP، یکی از مهم‌ترین سؤال‌های بدون جواب علوم کامپیوتری است. به بیانی دیگر اگر همیشه به این سادگی بتوان صحت یک پاسخ (نمونه حل) را بررسی کرد، آیا پیدا کردن راه‌حل نیز می‌تواند به آن سادگی باشد؟ برای این سؤال یک جایزه ۱ میلیون دلاری از طرف انسیتیتو ریاضی Clay در نظرگرفته شده‌است. | ## بخش 2: نظریه پیچیدگی محاسباتی | ما هیچ دلیلی برای قبول کردن آن نداریم ولی بین نظریه‌پردازان نیز این باور وجود دارد که باید جواب این سؤال منفی باشد بهینه‌سازی ترکیبی و الگوریتم‌های فرا ابتکاری، دکتر کوروش عشقی . پیچیدگی زمان پیچیدگی زمانی یک مسئله تعداد گام‌های مورد نیاز برای حل یک نمونه از یک مسئله به عنوان تابعی از اندازهٔ ورودی (معمولاً به وسیلهٔ تعداد بیت‌ها بیان می‌شود) به وسیلهٔ کارآمدترین الگوریتم می‌باشد. اگر یک مسئله پیچیدگی زمانی از مرتبه (O(n² روی یک کامپیوتر نمونه داشته باشد، معمولاً روی اکثر کامپیوترهای دیگر نیز پیچیدگی زمانی از مرتبه (O(n² خواهد داشت. پس این نشانه به ما کمک می‌کند که صرف نظر از یک کامپیوتر خاص، یک حالت کلی برای پیچیدگی زمانی یک الگوریتم ارائه دهیم. پیچیدگی رایانشی: هنگامی که یک الگوریتم خاص را تحلیل می‌کنیم، پیچیدگی زمانی (یا حافظه‌ای) یا مرتبه پیچیدگی زمانی آن را تعیین می‌کنیم. در تحلیل پیچیدگی رایانشی کوشش می‌کنیم تا حد پایینی کارایی همه الگوریتم‌ها را برای یک مسئله مفروض به دست آوریم. با مطالعه و مقایسه این الگوریتم‌ها، دیدی از چگونگی انتخاب از میان چند الگوریتم برای یک مسئله و بهبود بخشیدن به یک الگوریتم مفروض به دست می‌آوریم. دوم، مسئله مرتب‌سازی یکی از معدود مسائلی است که در بسط الگوریتم‌هایی با پیچیدگی زمانی نزدیک به حد پایینی از آن موفق بوده‌است. معرفی Np کامل تا این بخش از مقاله مسائلی معرفی شدند که اگر بتوان روشی برای حل آن‌ها حدس زد، در زمان نزدیک به زمان خطی یا حداقل در زمان چند جمله‌ای برحسب ورودی می‌توانستیم صحت راه‌حل را بررسی کنیم؛ ولی NP-Completeها مسائلی هستند که اثبات شده به سرعت قابل حل نیستند. بررسی ناکارآمد بودن زمانی مسائلی که در تئوری قابل حل شدن می‌باشند ولی در عمل نمی‌توان آن‌ها را حل کرد، محال یا ناشدنی می‌نامند. در حالت کلی فقط مسائلی که زمان آن‌ها به صورت Polynomial می‌باشد و اندازه ورودی آن‌ها در حد کوچک یا متوسط می‌باشد قابل حل شدن می‌باشند. | ## بخش 3: نظریه پیچیدگی محاسباتی | برای ملموس‌تر شدن این مسئله فرض کنید که یک مسئله مرحله لازم دارد تا حل شود (n اندازه ورودی می‌باشد). برای مقادیر کوچک n=۱۰۰ و با در نظر گرفتن کامپیوتری که (10 giga) عملیات را در یک ثانیه انجام می‌دهد، حل کردن این مسئله زمانی حدود سال طول خواهد کشید، که این زمان از عمر فعلی جهان بیشتر است! روش‌هایی برای حل مسائل NP-Complete به دلیل این که تعداد مسائل NP-Complete بسیار زیاد می‌باشد، شناختن این گونه مسائل به ما کمک می‌کند تا دست از پیدا کردن یک الگوریتم سریع و جامع برداریم و یکی از روش‌های زیر را امتحان کنیم: به کار بردن یک روش حدسی: یک الگوریتم که تا حد قابل قبولی در بیشتر موارد درست کار می‌کند، ولی تضمینی وجود ندارد که در همه موارد با سرعت قابل قبول نتیجه درستی تولید کند. حل کردن تقریبی مسئله به جای حل کردن دقیق آن: اغلب موارد این روش قابل قبول می‌باشد که با یک الگوریتم نسبتاً سریع یک مسئله را به‌طور تقریبی حل کنیم که می‌توان ثابت کرد جواب به‌دست آمده تقریباً نزدیک به جواب کاملاً صحیح می‌باشد. الگوریتم‌های زمان توانی را به کار ببریم: اگر واقعاً مجبور به حل کردن مسئله به‌طور کامل هستیم، می‌توان یک الگوریتم با زمان توانی نوشت و دیگر نگران پیدا کردن جواب بهتر نباشیم. از خلاصه کردن استفاده کنیم: خلاصه کردن به این مفهوم می‌باشد که از برخی اطلاعات غیرضروری می‌توان صرف نظر کرد. اغلب این اطلاعات برای پیاده‌سازی مسئله پیچیده در دنیای واقعی مورد نیاز می‌باشد، ولی در شرایطی که بخواهیم به نحوی مسئله را حل کنیم (حداقل به صورت تئوری و نه در عمل) می‌توان از برخی اطلاعات غیرضروری صرف نظر کرد. نمونه مسئله یک مسیر ساده در یک گراف به مسیری گفته می‌شود که هیچ راس یا یال تکراری در آن وجود نداشته‌ باشد. برای پیاده‌سازی مسئله ما به این احتیاج داریم که بتوانیم یک سؤال بلی/خیر طراحی کنیم. چون اگر مسیری به شما داده شود، به راحتی می‌توان طول مسیر را مشخص نمود و آن را با k مقایسه کرد. اگر چه می‌دانیم که این مسئله آیا در کلاس P می‌باشد یا نه، با این حال روش خاصی برای پیدا کردن مسیری با ویژگی‌های ذکر شده نیز بیان نشده‌است؛ و در حقیقت این مسئله جز NP-Completeها می‌باشد، پس می‌توان به این نتیجه نیز رسید که الگوریتمی کارآمد با چنان عملیات وجود ندارد. | ## جمع‌بندی | الگوریتم‌هایی وجود دارند که این مسئله را حل می‌کنند، به عنوان مثال همه مسیرهای موجود و ممکن را بررسی نموده و نتایج مقایسه شوند که آیا این مسیر مسئله را حل می‌کند یا نه.