我很困惑，这是我阅读后的想法：
P 在 NP 中，而 NP 在 NP-Complete 中。因此，所有 P 都可能是 NP 和 NP-Complete？
这是否意味着存在可能是 NP 和 NP-Complete 的排序算法？
希望这听起来不会太愚蠢。
问问题
8624 次
2 回答
9
首先要做的事情：
P 在 NP 中；NP是NP-Complete。因此，所有 P 都可能在 NP 和 NP-Complete 中？
这是一个很好的声明，因为您所说的暗示P=NP。没有人能够证明这一点或其他。所以这是事态：
大多数人相信P!=NP。引用维基百科：
在 2002 年对 100 名研究人员的民意调查中，61 人认为答案是否定的，9 人认为答案是肯定的，22 人不确定；8 认为这个问题可能独立于当前公认的公理，因此不可能证明或证伪。
一个简单的理解方法是：假设你得到了某个问题的解决方案。如果你能在多项式时间内验证解是否正确，那么问题就是NP。显然，可以在多项式时间内 (P) 解决的每个问题都在 NP 中（您可以自己解决问题并在 P 时间内与正确答案进行比较）。
现在我们有几个问题可以在多项式时间内验证，但不能同时解决。我们不确定是否永远不会有多项式时间解，或者我们现在还不能弄清楚。
排序数字
给定一个数字列表，您可以验证该列表是否在多项式时间内排序，因此问题显然是NP。
有已知的算法可以在多项式时间内对数字列表进行排序。（冒泡排序 O(n^2) 等）。因此问题是P。
希望这可以帮助。
考虑阅读此博客。
于 2012-12-12T11:04:08.263 回答
4
P、NP、NP-hard 和 NP-complete 是问题的复杂性类别；它们描述了一个问题，而不是算法。
于 2012-12-12T10:30:25.077 回答