runtime - np-complete 但不是“硬”

Question

是否有某种语言是 NP 完全的，但我们知道一些“快速”算法？我的意思不是像背包那样我们平均可以做得很好，我的意思是即使在最坏的情况下，运行时间也类似于 2^n^epsilon，结果对于任何 epsilon>0 都成立，所以我们可以让它任意接近0。

Answer 1

根据Wikipedia的说法，“还有一些 NP 难但不是 NP 完全的决策问题，例如停机问题。”

在我们知道“快速”算法的情况下，没有 NP 完备的语言；否则，它不会是 NP 完全的。

Answer 2

如果您确实找到了解决这个 np 完全问题的“快速”算法，那么您刚刚解决了 P=NP，并且如您所知，这仍然是一个悬而未决的问题。