我似乎无法真正理解说问题是 NP-Complete 的真正含义。谁能帮我解决以下问题？
NP完全问题是可以证明不存在在多项式时间内解决它的算法的问题。陈述是真的吗？
我想说这个说法是不正确的，因为任何人都可以真正证明对于任何 NP-Complete 问题都不存在这样的算法吗？通过环顾各种来源，我了解到对于任何 NP-Complete 问题都没有多项式时间算法；但是，无法证明。
任何帮助将不胜感激。谢谢。
问问题
760 次
2 回答
1
在某些情况下，可以证明不存在优于某个限制的算法。
例如，O(n log n)比较排序的界限已被证明。无论我们将来变得多么聪明，我们可以肯定没有人会发明O(n)比较分类。
但在这种情况下，没有人找到证据。但这并不意味着它不能被证明。
于 2012-10-31T18:18:41.350 回答
0
该陈述从根本上是错误的：有些问题无法在多项式时间内解决，这比 NP 问题要困难得多。NP 完备性的点是存在的多项式时间解等价于 P=NP（这另外意味着不存在的解意味着 P!=NP）。
于 2014-12-09T00:30:25.527 回答