فهرست مسئله‌های حل نشده در علوم رایانه
این یک فهرست از مسائل حل نشده در علوم رایانه است. یک مسئله، زمانی حل نشده در نظر گرفته می‌شود که یا راه‌حلی برای آن یافت نشده باشد و یا کارشناسان حوزه با راه‌حل‌های ارائه شده، مخالف باشند.
پیچیدگی محاسباتی
- مسئله‌ی P در مقابل NP
- آیا تابع یک‌طرفه وجود دارد؟
- آیا رمزنگاری کلید عمومی امکان‌پذیر است؟
- رابطه‌ی میان NP و BQP چیست؟
- مسئله‌ی NC = P
- مسئله‌ی NP = co-NP
- مسئله‌ی P = BPP
- مسئله‌ی P = PSPACE
- مسئله‌ی L = NL
- مسئله‌ی PH = PSPACE
- مسئله‌ی L = P
- مسئله‌ی L = RL
- حدس بازی‌های یکتا
- آیا فرضیه‌ی زمان اجرای نمایی درست است؟
- آیا فرضیه‌ی قوی زمان اجرای نمایی (SETH) درست است؟
- حدس Log-rank
زمان اجرای چندجمله‌ای در برابر غیرچندجمله‌ای برای مسائل الگوریتمی خاص
- آیا می‌توان مسئله‌ی تجزیه‌ی اعداد را در زمان اجرای چندجمله‌ای بر روی یک رایانه‌ی عادی (غیرکوانتومی) حل کرد؟
- آیا می‌توان لگاریتم گسسته را در زمان اجرای چندجمله‌ای محاسبه کرد؟
- آیا می‌توان کوتاه‌ترین بردار یک مشبکه را در زمان اجرای چندجمله‌ای بر روی یک رایانه‌ی عادی یا کوانتومی محاسبه کرد؟
- آیا می‌توان مسئله‌ی یک‌ریختی گراف را در زمان چندجمله‌ای حل کرد؟
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.