未解決的計算機科學問題

这个文章是在计算机科学中的有待解决的问题的列表。当该领域专家认为某些问题未解决，或当该领域中的几位专家不同意有关解决问题的办法时，这些计算机科学中的问题就被认为是未解决的。

计算复杂性理论

• P = NP问题。这是七个千禧年大奖难题之一
• NC (複雜度)
• NP = co-NP问题
• P = BPP问题
• P = PSPACE问题
• BQP和NP之间的关系是什么？

*

• 是真的吗？
• 单向函数存在吗？

算法

• 两个n位数乘法算法速度最快的是什么？
• 速度最快的矩阵乘法算法是什么？
• 可以在多项式时间内做整数分解吗？
• 可以在多项式时间内计算离散对数吗？
• 可以在多项式时间内解决吗？
• 可以在多项式时间内解决吗？
• 线性规划问题是否存在强多项式时间的解法？这是中的第9个问题。
• 快速傅里叶变换算法的复杂性上下限是什么？他们能比Θ（N log N）快吗？
• 可以在内解决3SUM问题吗？
• 伸展树

*

编程语言理论
*
*
*

其他问题
*

外部链接

• StackExchange上[http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science 计算机科学理论未解决的主要问题] 。
• Gerhard J. Woeginger的[http://www.cs.zju.edu.cn/people/yedeshi/algo09/reading/Open%20problems%20around%20exact%20algorithms.pdf 围绕精确算法的开放问题]，应用离散数学156 (2008) 397–405。
• [https://web.archive.org/web/20131104160106/http://www2.research.att.com/~dsj/nsflist.html 理论计算机科学面临的挑战]
• [http://maven.smith.edu/~orourke/TOPP/ 开放的问题项目] - 计算几何和相关的字段中的开放问题。
• [http://rtaloop.mancoosi.univ-paris-diderot.fr/ RTA列表的开放问题] - 重写逻辑中的开放问题。
• [http://tlca.di.unito.it/opltlca/ TLCA列表的开放问题] - 有类型λ演算领域中的开放问题。