是否有某种语言是 NP 完全的，但我们知道一些“快速”算法？我的意思不是像背包那样，我们平均可以做得很好，我的意思是即使在最坏的情况下，运行时间也类似于 2^n^epsilon，其中结果适用于任何 epsilon>0，所以我们可以允许它任意接近 0。
最佳答案
如果你确实找到了解决这个 np 完全问题的“快速”算法，那么你就解决了这个问题 P=NP，如您所知，这仍然是一个悬而未决的问题。
关于runtime - np 完成但不是 "hard"，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2914351/