具有超指数运行时的算法？

Question

前几天我和学生讨论了常见的复杂算法类,比如O(n),O(n ^k),O(n lg n),O(2 ⁿ),O(n!)等.我试图想出一个问题的例子,其中最着名的运行时是超指数的解决方案,例如O(2 ^{2 n}),但仍然是可判定的(例如,不是停止问题!)我知道的唯一例子是Presburger算术的可满足性,我认为任何介绍CS学生都不会真正理解或能够与之相关.

我的问题是,是否存在一个众所周知的问题,其最着名的解决方案是运行时超指数; 至少ω(n!)或ω(n ⁿ).我真的希望遇到这个描述有一些"合理"的问题,但我不知道.

Answer 1

最大简约性是找到连接n个DNA序列(代表物种)的进化树的问题,所述DNA序列需要最少的单核苷酸突变.n个给定序列被限制在叶子上出现; 树形拓扑和内部节点的序列是我们可以选择的.

在更多CS术语中:我们给出了一堆长度为k的字符串,它们必须出现在某些树的叶子上,我们必须为树中的每个内部节点选择一个树,加上长度为k的字符串,以便最小化所有边缘的汉明距离之和.

当还给出固定树时,可以使用Fitch算法非常有效地确定序列到内部节点的最佳分配.但是在通常情况下,没有给出树(即我们被要求找到最佳树),这使得问题NP难,这意味着原则上必须尝试每棵树.即使进化树具有根(代表假设的祖先),我们也只需要考虑不同的无根树,因为所需的最小突变数不受根的位置影响.对于n种,有3*5*7*...*(2n-5)叶标记的无根二叉树.(只有一种这样的树有3种,它有一个内部顶点和3个边缘;第4种可以插入3个边缘中的任何一个以产生一个独特的5边缘树;第5种可以插入任何树这5个边缘,依此类推 - 这个过程只生成一次所有树.)这有时是写的(2n-5)!! ,!! 意思是"双因子".

在实践中,使用分支和边界,并且在大多数真实数据集上,这设法避免评估大多数树.但高度"非树状"的随机数据需要全部或几乎全部(2n-5)!! 要检查的树木 - 因为在这种情况下,许多树木的最小突变计数几乎相等.

Answer 2

显示长度为n的字符串的所有排列是n !,找到哈密尔顿循环是n !,最小图着色,....

编辑:更快的阿克曼功能.事实上,他们似乎没有约束功能.

A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.

from wiki:
A(4,3) = 2^2^65536,...

Answer 3

计算实数到一定精度的算法是否有效？曼德尔布罗特集面积的公式收敛得极其缓慢；两位数有10 ^{118 个}术语，三位数有10 ^{1181 个术语。}