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

هیچ تغییری در اندازه به وجود نیامده‌ است. ،  ۳ سال پیش
جز
سوال به سؤال، replaced: سوال ← سؤال (6) با استفاده از AWB
جز (اصلاح پیوند به صفحه ابهام‌زدایی با استفاده از AWB)
جز (سوال به سؤال، replaced: سوال ← سؤال (6) با استفاده از AWB)
مواردی هست که میدانیم یک مسئله جواب دارد ولی راه حل و روش حل آن هنوز ارائه نگردیده و گاهی علاوه بر مشکل مذکور حتی با در دست داشتن راه حل، منابع و ابزار لازم جهت پیاده‌سازی آن مسئله را نداریم.
 
بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سوالسؤال به نظر طبیعی می‌رسد که [[درجه سختی]] مساله چقدر است. نظریه پیچیدگی محاسبات در این زمینه‌است.
 
برای سادگی کار مساله‌ها به کلاس‌هایی تقسیم می‌شوند، طوری که مساله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح [[کلاس‌های پیچیدگی]] خوانده می‌شوند.
 
== آیا P=NP است؟ ==
برابر بودن مسائل کلاس P دقیقا همان مسائل کلاس NP، یکی از مهم‌ترین سوال‌هایسؤال‌های بدون جواب علوم کامپیوتری است. به بیانی دیگر اگر همیشه به این سادگی بتوان صحت یک راه‌حل را بررسی کرد، آیا پیدا کردن راه‌حل نیز می‌تواند به آن سادگی باشد؟ برای این سوالسؤال یک جایزه ۱ میلیون دلاری از طرف [http://www.claymath.org/millennium انسیتیتو ریاضی Clay] در نظرگرفته شده‌است. ما هیچ دلیلی برای قبول کردن آن نداریم ولی بین نظریه‌پردازان نیز این باور وجود دارد که باید جواب این سوالسؤال منفی باشد{{مدرک}}. همچنین دلیلی برای رد کردن آن نیز وجود ندارد.
 
== [[پیچیدگی زمانی]] ==
 
== نمونه مساله ==
یک مسیر ساده در یک گراف به مسیری اطلاق می‌شود که هیچ راس یا یال تکراری در آن وجودنداشته‌باشد. برای پیاده‌سازی مساله ما به این احتیاج داریم که بتوانیم یک سوالسؤال بلی/خیر طراحی کنیم. با داشتن گراف G، رئوس s و t و عدد k آیا یک مسیر ساده از s به t با حداقل k یال وجوددارد؟ راه‌حل این مساله جواب سوالسؤال خواهد بود.
چرا این مساله NP می‌باشد؟ چون اگر مسیری به شما داده شود، به راحتی می‌توان طول مسیر را مشخص نمود و آن را با k مقایسه کرد. همه این کارها در زمان خطی و صد البته در زمان Polynomial قابل انجام می‌باشد.
اگر چه می‌دانیم که این مساله آیا در کلاس P می‌باشد یا نه، با این حال روش خاصی برای پیدا کردن مسیری با ویژگی‌های ذکر شده نیز بیان نشده‌است؛ و در حقیقت این مساله جز NP-Completeها می‌باشد، پس می‌توان به این نتیجه نیز رسید که الگوریتمی کارآمد با چنان عملیات وجود ندارد.