未解決的電腦科學問題

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

計算複雜性理論

• 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列表的開放問題 （頁面存檔備份，存於互聯網檔案館） - 有類型λ演算領域中的開放問題。