np-complete 但不“难”
是否有一些语言是 NP 完全的，但我们知道一些“快速”算法？我的意思不是像背包那样我们平均可以做得很好，我的意思是即使在最坏的情况下，运行时间也类似于 2^n^epsilon，其中结果适用于任何 epsilon>0，所以我们可以允许它任意接近0。
Is there some language that is NP-complete but for which we know some "quick" algorithm? I don't mean like the ones for knapsack where we can do well on average, I mean that even in the worst case the runtime is something like 2^n^epsilon, where the result holds for any epsilon>0 and so we can allow it to get arbitrarily close to 0.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果你确实找到了解决这个 np 完全问题的“快速”算法，那么你就解决了这个问题
P=NP，正如你所知，这仍然是一个悬而未决的问题。
If you do find a "quick" algorithm to this np-complete problem, you just solved that
P=NP, and as you know, that is still an open question.
根据 维基百科，“也有一些决策问题是 NP 困难的，但不是 NP -完整，例如停机问题。”
没有一种语言是 NP 完全的，我们知道“快速”算法；否则，它就不是 NP 完全的。
According to Wikipedia, "There are also decision problems that are NP-hard but not NP-complete, for example the halting problem."
There are no languages that are NP complete where we know a "quick" algorithm; otherwise, it wouldn't be NP-complete.