psi*_*lia 5 theory big-o time-complexity
在给定无限数量的处理单元和无限空间的情况下,是否有可能在合理的时间内解决O(n!)复杂度问题？
O(n!)问题的典型例子是强力搜索:尝试所有排列(有序组合).
确实是.考虑一下严格的NP形式的旅行商问题:给出从每个点到另一个点旅行的成本列表,你能组合一个成本低于K的旅游吗？使用英特尔的新型无限核心CPU,您只需为每个可能的排列分配一个核心,并将成本加起来(这很快),并查看是否有任何核心成功.
更一般地,NP中的问题是决策问题,使得可以在多项式时间(即,有效地)验证潜在的解决方案,并且因此(因为潜在的解决方案是可枚举的)可以利用足够多的CPU有效地解决任何这样的问题.
听起来你真正想的是在非确定性机器上是否可以将O(n!)复杂度的问题减少到O(n ^ a); 换句话说,Not-P = NP.这个问题的答案是否定的,有一些不是NP的Not-P问题.例如,有限的暂停问题(询问程序是否最多停止n步骤).