未解決的電腦科學問題
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此條目可參照英語維基百科相應條目來擴充。 |
這個文章是在電腦科學中的有待解決的問題的列表。當該領域專家認為某些問題未解決,或當該領域中的幾位專家不同意有關解決問題的辦法時,這些電腦科學中的問題就被認為是未解決的。
計算複雜性理論
- P = NP問題。這是七個千禧年大獎難題之一
- NC (複雜度)
- NP = co-NP問題
- P = BPP問題
- P = PSPACE問題
- BQP和NP之間的關係是什麼?
- 獨特遊戲猜想
- 指數時間假說是真的嗎?
- 單向函式存在嗎?
演算法
- 兩個n位數乘法演算法速度最快的是什麼?
- 速度最快的矩陣乘法演算法是什麼?
- 可以在多項式時間內做整數分解嗎?
- 可以在多項式時間內計算離散對數嗎?
- 可以在多項式時間內解決圖同構問題嗎?
- 可以在多項式時間內解決奇偶校驗遊戲嗎?
- 線性規劃問題是否存在強多項式時間的解法?這是Smale問題列表中的第9個問題。
- 快速傅立葉變換演算法的複雜性上下限是什麼?他們能比Θ(N log N)快嗎?
- 可以在次二次時間內解決3SUM問題嗎?
- 伸展樹動態最佳性猜想
- K-伺服器問題
程式語言理論
其他問題
外部連結
- StackExchange上電腦科學理論未解決的主要問題 (頁面存檔備份,存於網際網路檔案館)。
- Gerhard J. Woeginger的圍繞精確演算法的開放問題[永久失效連結],應用離散數學156 (2008) 397–405。
- 理論電腦科學面臨的挑戰
- 開放的問題專案 (頁面存檔備份,存於網際網路檔案館) - 計算幾何和相關的欄位中的開放問題。
- RTA列表的開放問題 (頁面存檔備份,存於網際網路檔案館) - 重寫邏輯中的開放問題。
- TLCA列表的開放問題 (頁面存檔備份,存於網際網路檔案館) - 有類型λ演算領域中的開放問題。