人们普遍认为，可以在多项式时间内解决的问题是“易处理的”，而需要比这更多时间的算法是难处理的。当然，在多项式时间内可解并不能说明绝对效率。例如，在时间 n1000 中运行的东西在实践中是完全不切实际的。
虽然我见过相当多的多项式时间算法，但我从未见过一个实际问题的运行时间超过 O(n4)，这是原始版本Edmonds 的匹配算法。
我的问题是:是否存在一个众所周知的问题，其最佳多项式时间算法对于实际输入是完全不切实际的？显然，我们可以构造完全无用的简单人为问题，但我很好奇是否存在一个著名的问题，其中最著名的解决方案既是多项式时间又是完全不可行的。
编辑:为了澄清，我可能应该说我正在寻找一种对问题规模有巨大指数的算法，而不是难以实现的算法或具有巨大问题规模的算法常数因子。正如 Moron 指出的那样，有许多著名的不切实际的算法具有很好的渐近行为。
最佳答案
PRIMES 在 P 中:AKS primality test ，复杂度 O(n6)，其中 n = log N 是用于编码候选素数的位数。
虽然这是一个漂亮的理论结果，但通常使用 Miller-Rabin 执行素数测试。测试，或与其他类似的随机算法。
关于algorithm - 已知在 P 中的不切实际算法的示例？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5140015/