未解決的計算機科學問題

這個文章是在計算機科學中的有待解決的問題的列表。當該領域專家認為某些問題未解決，或當該領域中的幾位專家不同意有關解決問題的辦法時，這些計算機科學中的問題就被認為是未解決的。

計算複雜性理論

• P = NP問題。這是七個千禧年大獎難題之一
• NC (複雜度)
• NP = co-NP問題
• P = BPP問題
• P = PSPACE問題
• BQP和NP之間的關係是什麼？
• 獨特遊戲猜想
• 指數時間假說是真的嗎？
• 單向函數存在嗎？

算法

• 兩個n位數乘法算法速度最快的是什麼？
• 速度最快的矩陣乘法算法是什麼？
• 可以在多項式時間內做整數分解嗎？
• 可以在多項式時間內計算離散對數嗎？
• 可以在多項式時間內解決圖同構問題嗎？
• 可以在多項式時間內解決奇偶校驗遊戲嗎？
• 線性規劃問題是否存在強多項式時間的解法？這是Smale問題列表中的第9個問題。
• 快速傅里葉變換算法的複雜性上下限是什麼？他們能比Θ（N log N）快嗎？
• 可以在次二次時間內解決3SUM問題嗎？
• 伸展樹動態最優性猜想
• K-服務器問題

編程語言理論

• POPLmark
• Barendregt–Geuvers–Klop猜想
• 廣義星高問題

其他問題

• Aanderaa–Karp–Rosenberg猜想

外部連結

• StackExchange上計算機科學理論未解決的主要問題 （頁面存檔備份，存於網際網路檔案館）。
• Gerhard J. Woeginger的圍繞精確算法的開放問題，應用離散數學156 (2008) 397–405。
• 理論計算機科學面臨的挑戰
• 開放的問題項目 （頁面存檔備份，存於網際網路檔案館） - 計算幾何和相關的字段中的開放問題。
• RTA列表的開放問題 （頁面存檔備份，存於網際網路檔案館） - 重寫邏輯中的開放問題。
• TLCA列表的開放問題 （頁面存檔備份，存於網際網路檔案館） - 有類型λ演算領域中的開放問題。