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

هیچ تغییری در اندازه به وجود نیامده‌ است. ،  ۳ سال پیش
جز
اصلاح غلط املایی مساله، مسئله>>>>>>مسأله با استفاده از AWB
جز (اصلاح غلط املایی مساله، مسئله>>>>>>مسأله با استفاده از AWB)
'''نظریهٔ پیچیدگی محاسباتی''' شاخه‌ای از [[نظریه محاسبات|نظریهٔ محاسبات]]، [[علوم نظری رایانه]] و [[ریاضی]] است که به بررسی دشواری حل مسائل به وسیلهٔ [[رایانه]] (به عبارت دقیق‌تر به صورت [[الگوریتم|الگوریتمی]]) می‌پردازد. این نظریه بخشی از [[نظریه محاسبات|نظریهٔ محاسباتی]] است که با منابع مورد نیاز برای حل یک مسالهمسأله سروکار دارد.
 
== مقدمه ==
 
عمومی‌ترین منابع، زمان (مقدار زمان مورد نیاز برای حل مسالهمسأله) و فضا (مقدار حافظه مورد نیاز) می‌باشند. از سایر منابع می‌تواند به تعداد پردازنده‌های موازی (در حالت [[پردازش موازی]]) و... اشاره کرد. اما در اینجا عوامل بالا مورد بحث نیستند. باید به این نکته توجه داشت که نظریه پیچیدگی با [[نظریه قابل حل بودن]] متفاوت است. این نظریه در مورد قابل حل بودن یک مسالهمسأله بدون توجه به منابع مورد نیاز آن، بحث می‌کند.
مواردی هست که میدانیم یک مسئلهمسأله جواب دارد ولی راه حل و روش حل آن هنوز ارائه نگردیده و گاهی علاوه بر مشکل مذکور حتی با در دست داشتن راه حل، منابع و ابزار لازم جهت پیاده‌سازی آن مسئلهمسأله را نداریم.
 
بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سؤال به نظر طبیعی می‌رسد که [[درجه سختی]] مسالهمسأله چقدر است. نظریه پیچیدگی محاسبات در این زمینه‌است.
 
برای سادگی کار مساله‌هامسأله‌ها به کلاس‌هایی تقسیم می‌شوند، طوری که مساله‌هایمسأله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح [[کلاس‌های پیچیدگی]] خوانده می‌شوند.
 
بعضی منابع دیگری که در این نظریه مورد بررسی قرار می‌گیرند، مثل [[عدم تعین]] صرفاً جنبهٔ آموزشی دارند ولی بررسی آن‌ها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.
 
معروف‌ترین کلاس‌های پیچیدگی، '''P''' و '''NP''' هستند که مساله‌هامسأله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت '''P''' کلاس مساله‌هاییمسأله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما '''NP''' شامل آن دسته از مساله‌هاستمسأله‌هاست که اگرچه ممکن است پیدا کردن جواب برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیلهٔ یک [[کارایی الگوریتم‌ها|الگوریتم سریع]] ممکن است.
البته کلاس‌های پیچیدگی به مراتب سخت‌تری از '''NP''' نیز وجود دارند.
* '''P-SPACE''': مسائلی که با اختصاص دادن مقدار کافی حافظه (که این مقدار حافظه معمولاً تابعی از اندازه مسالهمسأله می‌باشد) بدون در نظر گرفتن زمان مورد نیاز به حل آن، می‌توانند حل شوند.
* '''EXP-TIME''': مسائلی که زمان مورد نیاز برای حل آنها به صورت توانی می‌باشد. مسائل این کلاس شامل همه مسائل سه کلاس بالایی نیز می‌باشد. نکته جالب و قابل توجه این است که حتی این کلاس نیز جامع نمی‌باشد. یعنی مسائلی وجود دارند که بهترین و کارامدترین الگوریتم‌ها نیز زمان بیش‌تری نسبت به زمان توانی می‌گیرند.
* '''Un-decidable''' یا '''غیرقابل تصمیم‌گیری''': برای برخی از مسائل می‌توانیم اثبات کنیم که الگوریتمی را نمی‌شود پیدا کرد که همیشه آن مسالهمسأله را حل می‌کند، بدون در نظر گرفتن فضا و زمان. در این زمینه آقای [[ریچارد لیپتون]] (از صاحب‌نظران این زمینه) در مقاله‌ای نوشته‌اند: یک روش اثبات غیررسمی برای این مسالهمسأله می‌تواند این باشد: تعداد زیادی مساله،مسأله، مثلاً به زیادی اعداد حقیقی وجود دارند، ولی تعداد برنامه‌هایی که مسائل را حل می‌کنند در حد اعداد صحیح هستند. اما ما همیشه می‌توانیم مسائل کاربردی و مهمی را پیدا کنیم که قابل حل نیستند.
 
== آیا P=NP است؟ ==
== [[پیچیدگی زمانی]] ==
 
پیچیدگی زمانی یک مسالهمسأله تعداد گام‌های مورد نیاز برای حل یک نمونه از یک مسالهمسأله به عنوان [[تابع|تابعی]] از اندازهٔ ورودی (معمولاً بوسیله تعداد [[بیت (رایانه)|بیت‌ها]] بیان می‌شود) بوسیله کارآمدترین الگوریتم می‌باشد. برای درک بهتر این مساله،مسأله، فرض کنید که یک مسالهمسأله با ورودی n بیت در n² گام حل شود. در این مثال می‌گوییم که مسالهمسأله از درجه پیچیدگی n² می‌باشد. البته تعداد دقیق گام‌ها بستگی به ماشین و زبان مورد استفاده دارد. اما برای صرف نظر کردن از این مشکل، [[نماد O بزرگ]] (Big O notation) معمولاً بکار می‌رود. اگر یک مسالهمسأله پیچیدگی زمانی از مرتبه (O(n² روی یک کامپیوتر نمونه داشته باشد، معمولاً روی اکثر کامپیوترهای دیگر نیز پیچیدگی زمانی از مرتبه (O(n² خواهدداشت. پس این نشانه به ما کمک می‌کند که صرف نظر از یک کامپیوتر خاص، یک حالت کلی برای پیچیدگی زمانی یک الگوریتم ارائه دهیم.{{سخ}}
پیچیدگی محاسباتی:{{سخ}}
هنگامی که یک الگوریتم خاص را تحلیل می‌کنیم، پیچیدگی زمانی (یا حافظه‌ای) یا مرتبه پیچیدگی زمانی آن را تعیین می‌کنیم. عبارت است از مطالعهٔ تمام الگوریتم‌های امکانپذبر برای حل یک مسئلهمسأله مفروض است. در تحلیل پیچیدگی محاسباتی کوشش می‌کنیم تا حد پایینی کارایی همه الگوریتم‌ها را برای یک مسئلهمسأله مفروض به دست آوریم.{{سخ}}
تحلیل پیچیدگی محاسباتی را با مطالعهٔ مسئلهمسأله مرتب‌سازی معرفی می‌کنیم. دو دلیل برای انتخاب مسئلهمسأله وجود دارد. نخست چند الگوریتم ابداع شده‌اند که مسئلهمسأله را حل می‌کنند. با مطالعه و مقایسه این الگوریتم‌ها، دیدی از چگونگی انتخاب از میان چند الگوریتم برای یک مسئلهمسأله و بهبود بخشیدن به یک الگوریتم مفروض به دست می‌آوریم.{{سخ}}
دوم، مسئلهمسأله مرتب‌سازی یکی از معدود مسائلی است که در بسط الگوریتم‌هایی با پیچیدگی زمانی نزدیک به حد پایینی از آن موفق بوده است.
 
== معرفی [[Np کامل]] ==
 
تا این بخش از مقاله مسائلی معرفی شدند که اگر بتوان روشی برای حل آنها حدس زد، در زمان نزدیک به زمان خطی و یا حداقل در زمان چند جمله‌ای برحسب ورودی می‌توانستیم صحت راه‌حل را بررسی کنیم؛ ولی '''NP-Complete'''ها مسائلی هستند که اثبات شده به سرعت قابل حل نیستند.
در تئوری پیچیدگی NP-Completeها دشوارترین مسائل کلاس NP هستند و جزء مسائلی می‌باشند که احتمال حضورشان در کلاس P خیلی کم است. علت این امر این می‌باشد که اگر یک راه‌حل پیدا شود که بتواندیک مسالهمسأله NP-Complete را حل کند، می‌توان از آن الگوریتم برای حل کردن سریع همه مسائل NP-Complete استفاده کرد. به خاطر این مسالهمسأله و نیز بخاطر اینکه تحقیقات زیادی برای پیدا کردن الگوریتم کارآمدی برای حل کردن اینگونه مسائل با شکست مواجه شده‌اند، وقتی که مساله‌ایمسأله‌ای به عنوان NP-Complete معرفی شد، معمولاً اینطور قلمداد می‌شود که این مسالهمسأله در زمان Polynomial قابل حل شدن نمی‌باشد، یا به بیانی دیگر هیچ الگوریتمی وجود ندارد که این مسالهمسأله را در زمان Polynomial حل نماید.
کلاس متشکل از مسائل '''NP-Complete''' با نام '''NP-C''' نیز خوانده می‌شود.
 
== بررسی ناکارآمد بودن زمانی ==
مسائلی که در تئوری قابل حل شدن می‌باشند ولی در عمل نمی‌توان آنها را حل کرد، محال یا ناشدنی می‌نامند. در حالت کلی فقط مسائلی که زمان آنها به صورت Polynomial می‌باشد و اندازه ورودی آنها در حد کوچک یا متوسط می‌باشد قابل حل شدن می‌باشند. مسائلی که زمان آنها به صورت توانی (EXPTIME-complete) می‌باشند به عنوان مسائل محال یا ناشدنی شناخته شده‌اند. همچنین اگر مسائل رده NP جز مسائل رده P نباشند، مسائل NP-Complete نیز به عنوان محال یا نشدنی خواهند بود.
برای ملموس‌تر شدن این مسالهمسأله فرض کنید که یک مسالهمسأله <math>2^n</math> مرحله لازم دارد تا حل شود (n اندازه ورودی می‌باشد). برای مقادیر کوچک n=۱۰۰ و با در نظر گرفتن کامپیوتری که <math>10^{10}</math> (10 giga) عملیات را در یک ثانیه انجام می‌دهد، حل کردن این مسالهمسأله زمانی حدود <math>10^{12}*4</math> سال طول خواهد کشید، که این زمان از عمر فعلی جهان بیشتر است!
 
== روش‌هایی برای حل مسائل NP-Complete ==
به خاطر اینکه تعداد مسائل NP-Complete بسیار زیاد می‌باشد، شناختن اینگونه مسائل به ما کمک می‌کند تا دست از پیدا کردن یک الگوریتم سریع و جامع برداریم و یکی از روش‌های زیر را امتحان کنیم:
* '''به کار بردن یک روش حدسی''': یک الگوریتم که تا حد قابل قبولی در بیشتر موارد درست کار می‌کند، ولی تضمینی وجود ندارد که در همه موارد با سرعت قابل قبول نتیجه درستی تولید کند.
* '''حل کردن تقریبی مسالهمسأله به جای حل کردن دقیق آن''': اغلب موارد این روش قابل قبول می‌باشد که با یک الگوریتم نسبتاً سریع یک مسالهمسأله را به طور تقریبی حل کنیم که می‌توان ثابت کرد جواب بدست آمده تقرییا نزدیک به جواب کاملاً صحیح می‌باشد.
* '''الگوریتم‌های زمان توانی را به کار ببریم''': اگر واقعا مجبور به حل کردن مسالهمسأله به طور کامل هستیم، می‌توان یک الگوریتم با زمان توانی نوشت و دیگر نگران پیدا کردن جواب بهتر نباشیم.
* '''از خلاصه کردن استفاده کنیم''': خلاصه کردن به این مفهوم می‌باشد که از برخی اطلاعات غیرضروری می‌توان صرف نظر کرد. اغلب این اطلاعات برای پیاده‌سازی مسالهمسأله پیچیده در دنیای واقعی مورد نیاز می‌باشد، ولی در شرایطی که بخواهیم به نحوی مسالهمسأله را حل کنیم (حداقل به صورت تئوری و نه در عمل) می‌توان از برخی اطلاعات غیرضروری صرف نظر کرد.
 
== نمونه مسالهمسأله ==
یک مسیر ساده در یک گراف به مسیری اطلاق می‌شود که هیچ راس یا یال تکراری در آن وجودنداشته‌باشد. برای پیاده‌سازی مسالهمسأله ما به این احتیاج داریم که بتوانیم یک سؤال بلی/خیر طراحی کنیم. با داشتن گراف G، رئوس s و t و عدد k آیا یک مسیر ساده از s به t با حداقل k یال وجوددارد؟ راه‌حل این مسالهمسأله جواب سؤال خواهد بود.
چرا این مسالهمسأله NP می‌باشد؟ چون اگر مسیری به شما داده شود، به راحتی می‌توان طول مسیر را مشخص نمود و آن را با k مقایسه کرد. همه این کارها در زمان خطی و صد البته در زمان Polynomial قابل انجام می‌باشد.
اگر چه می‌دانیم که این مسالهمسأله آیا در کلاس P می‌باشد یا نه، با این حال روش خاصی برای پیدا کردن مسیری با ویژگی‌های ذکر شده نیز بیان نشده‌است؛ و در حقیقت این مسالهمسأله جز NP-Completeها می‌باشد، پس می‌توان به این نتیجه نیز رسید که الگوریتمی کارآمد با چنان عملیات وجود ندارد.
الگوریتم‌هایی وجود دارند که این مسالهمسأله را حل می‌کنند، به عنوان مثال همه مسیرهای موجود و ممکن را بررسی نموده و نتایج مقایسه شوند که آیا این مسیر مسالهمسأله را حل می‌کند یا نه. اما تا آنجایی که می‌دانیم، الگوریتمی با زمان Polynomial برای حل این مسالهمسأله وجود ندارد.
 
== جستارهای وابسته ==