Nik*_*nka 5 algorithm np-complete np
计算机科学中是否存在任何只能在双指数时间内解决的重大问题？如果它们存在,那么它们属于哪类问题？
小智 9
来自维基百科:
在计算复杂性理论中,一些算法采用双指数时间:
Presburger算法的每个决策程序可证明至少需要双指数时间
在一个领域计算Gröbner基础.在最坏的情况下,Gröbner基础可能有许多元素,这些元素在变量数量上是双指数的.
寻找一整套关联交换的统一者
满意CTL +(事实上,2-EXPTIME完成)
实际闭合场上的量词消除需要双倍指数时间(参见圆柱代数分解).
计算正则表达式的补码
归档时间：
13 年，4 月 前
查看次数：
680 次
最近记录：