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

(نجات ۱ منبع و علامت‌زدن ۰ به‌عنوان مرده.) #IABot (v2.0)
 
دقیقاً برابر بودن مسائل کلاس P با مسائل کلاس NP، یکی از مهم‌ترین سؤال‌های بدون جواب علوم کامپیوتری است. به بیانی دیگر اگر همیشه به این سادگی بتوان صحت یک راه‌حل را بررسی کرد، آیا پیدا کردن راه‌حل نیز می‌تواند به آن سادگی باشد؟ برای این سؤال یک جایزه ۱ میلیون دلاری از طرف [http://www.claymath.org/millennium انسیتیتو ریاضی Clay] در نظرگرفته شده‌است. ما هیچ دلیلی برای قبول کردن آن نداریم ولی بین نظریه‌پردازان نیز این باور وجود دارد که باید جواب این سؤال منفی باشد{{<ref>بهینه‌سازی ترکیبی و الگوریتم‌های فرا ابتکاری، دکتر کوروش عشقی</ref>}}. همچنین دلیلی برای رد کردن آن نیز وجود ندارد.
 
== [[پیچیدگی زمانی|یپیچیدگی زمان]] ==
پیچیدگی زمانی یک مسئله تعداد گام‌های مورد نیاز برای حل یک نمونه از یک مسئله به عنوان [[تابع|تابعی]] از اندازهٔ ورودی (معمولاً به وسیلهٔ تعداد [[بیت (رایانه)|بیت‌ها]] بیان می‌شود) به وسیلهٔ کارآمدترین الگوریتم می‌باشد. برای درک بهتر این مسئله، فرض کنید که یک مسئله با ورودی n بیت در n² گام حل شود. در این مثال می‌گوییم که مسئله از درجه پیچیدگی n² می‌باشد. البته تعداد دقیق گام‌ها بستگی به ماشین و زبان مورد استفاده دارد. اما برای صرف نظر کردن از این مشکل، [[نماد O بزرگ]] (Big O notation) معمولاً بکار می‌رود. اگر یک مسئله پیچیدگی زمانی از مرتبه (O(n² روی یک کامپیوتر نمونه داشته باشد، معمولاً روی اکثر کامپیوترهای دیگر نیز پیچیدگی زمانی از مرتبه (O(n² خواهدداشت. پس این نشانه به ما کمک می‌کند که صرف نظر از یک کامپیوتر خاص، یک حالت کلی برای پیچیدگی زمانی یک الگوریتم ارائه دهیم.{{سخ}}
پیچیدگی محاسباتی:{{سخ}}
کاربر گمنام