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

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