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