人们普遍认为,在多项式时间内可以解决的问题是"易处理的",而需要比这更长时间的算法是难以处理的.当然,在多项式时间内可解决的问题绝不是绝对的效率; 例如,在时间n 1000中运行的东西在实践中是完全不切实际的.
虽然我已经看到了相当数量的多项式时间算法,但我从来没有见过一个超过O(n 4)的实际问题,这是Edmonds匹配算法的原始版本.
我的问题是:是否存在一个众所周知的问题,其最佳多项式时间算法对于实际输入是完全不切实际的？显然,我们可以构造完全无用的简单设计问题,但我很好奇是否有一个着名的问题,其中最着名的解决方案是多项式时间和完全不可行.
编辑:为了澄清,我应该说我正在寻找一个在问题规模上有巨大指数的算法,而不是一个难以实现的算法或一个具有巨大常数因子的算法.正如莫伦指出的那样,有许多着名的不切实际的算法具有很好的渐近行为.
mac*_*ksk 10
PRIMES在P:AKS素性测试中,复杂度为O(n 6),其中n = log N是用于编码主要候选者的比特数.
虽然这是一个很好的理论结果,但通常使用Miller-Rabin测试或其他随机算法进行素数测试.