6

计算机科学中是否有任何重大问题只能在双指数时间内解决？如果它们存在，那么它们属于哪一类问题？

4

1 回答 1

10

来自维基百科：

在计算复杂性理论中，一些算法需要双指数时间：

  • Presburger 算术的每个决策过程可证明至少需要双指数时间

  • 计算场上的 Gröbner 基。在最坏的情况下，Gröbner 基可能有许多元素，这些元素的变量数量是双指数的。

  • 找到一组完整的关联交换统一符

  • 满足 CTL+（实际上是 2-EXPTIME-complete）

  • 实封闭场上的量词消除需要双指数时间（请参阅圆柱代数分解）。

  • 计算正则表达式的补码

于 2013-02-11T17:45:21.980 回答