未解决的电脑科学问题
 | 此条目可参照英语维基百科相应条目来扩充。 |
这个文章是在电脑科学中的有待解决的问题的列表。当该领域专家认为某些问题未解决，或当该领域中的几位专家不同意有关解决问题的办法时，这些电脑科学中的问题就被认为是未解决的。
计算复杂性理论[编辑]
- 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列表的开放问题 （页面存档备份，存于互联网档案馆） - 有类型λ演算领域中的开放问题。