فهرست مسئله‌های حل‌نشده در علوم رایانه

این یک فهرست از مسائل حل نشده در علوم رایانه است. یک مسئله، زمانی حل نشده در نظر گرفته می‌شود که یا راه‌حلی برای آن یافت نشده باشد و یا کارشناسان حوزه با راه‌حل‌های ارائه شده، مخالف باشند.

 پیچیدگی محاسباتی 

 مسئله‌ی P در مقابل NP
 آیا تابع یک‌طرفه وجود دارد؟
 آیا رمزنگاری کلید عمومی امکان‌پذیر است؟
 رابطه‌ی میان NP و BQP چیست؟
 مسئله‌ی NC = P
 مسئله‌ی NP = co-NP
 مسئله‌ی P = BPP
 مسئله‌ی P = PSPACE
 مسئله‌ی L = NL
 مسئله‌ی PH = PSPACE
 مسئله‌ی L = P
 مسئله‌ی L = RL
 حدس بازی‌های یکتا
 آیا فرضیه‌ی زمان اجرای نمایی درست است؟
 آیا فرضیه‌ی قوی زمان اجرای نمایی (SETH) درست است؟
 حدس Log-rank

 زمان اجرای چندجمله‌ای در برابر غیرچندجمله‌ای برای مسائل الگوریتمی خاص 
 آیا می‌توان مسئله‌ی تجزیه‌ی اعداد را در زمان اجرای چندجمله‌ای بر روی یک رایانه‌ی عادی (غیرکوانتومی) حل کرد؟
 آیا می‌توان لگاریتم گسسته را در زمان اجرای چندجمله‌ای محاسبه کرد؟
 آیا می‌توان کوتاه‌ترین بردار یک مشبکه را در زمان اجرای چندجمله‌ای بر روی یک رایانه‌ی عادی یا کوانتومی محاسبه کرد؟
 آیا می‌توان مسئله‌ی یک‌ریختی گراف را در زمان چندجمله‌ای حل کرد؟

 منابع 

صفحه‌ی ویکی‌پدیای انگلیسی

رده:حدس‌ها
رده:فهرست‌های مسئله‌های حل‌نشده
رده:مسئله‌های حل‌نشده
رده:مسئله‌های حل‌نشده در علوم رایانه