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

* '''Un-decidable''' یا '''غیرقابل تصمیم‌گیری''': برای برخی از مسائل می‌توانیم اثبات کنیم که الگوریتمی را نمی‌شود پیدا کرد که همیشه آن مسئله را حل می‌کند، بدون در نظر گرفتن [[فضا و زمان]]. به عقیده [[ریچارد لیپتون]] (از صاحب‌نظران این زمینه): یک [[روش اثبات]] غیررسمی برای این مسئله می‌تواند این باشد: تعداد زیادی مسئله، مثلاً به زیادی [[اعداد حقیقی]] وجود دارند، ولی تعداد برنامه‌هایی که مسائل را حل می‌کنند در حد [[اعداد صحیح]] هستند. اما ما همیشه می‌توانیم مسائل کاربردی و مهمی را پیدا کنیم که قابل حل نیستند.

 

دقیقاً برابر بودن مسائل کلاس P با مسائل کلاس NP، یکی از مهم‌ترین سؤال‌های بدون جواب علوم کامپیوتری است. به بیانی دیگر اگر همیشه به این سادگی بتوان صحت یک راه‌حل را بررسی کرد، آیا پیدا کردن راه‌حل نیز می‌تواند به آن سادگی باشد؟ برای این سؤال یک جایزه ۱ میلیون دلاری از طرف [http://www.claymath.org/millennium انسیتیتو ریاضی Clay] در نظرگرفته شده‌است. ما هیچ دلیلی برای قبول کردن آن نداریم ولی بین نظریه‌پردازان نیز این باور وجود دارد که باید جواب این سؤال منفی باشد{{<ref>بهینه‌سازی ترکیبی و الگوریتم‌های فرا ابتکاری، دکتر کوروش عشقی</ref>}}. همچنین دلیلی برای رد کردن آن نیز وجود ندارد.