فهرست مسئله‌های حل‌نشده در علوم رایانه - ویکی‌پدیا، دانشنامهٔ آزاد

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

پیچیدگی محاسباتی[ویرایش]

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

زمان اجرای چندجمله‌ای در برابر غیرچندجمله‌ای برای مسائل الگوریتمی خاص[ویرایش]

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

منابع[ویرایش]

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