一些排序算法可以是P，NP或NP-Complete吗？

Question

经过一些阅读，我感到很困惑：

P在NP中，而NP在NP-Complete中。那么所有的P都可能在NP和NP-Complete中吗？

这是否意味着有可能存在既是NP又是NP-Complete的排序算法？

希望这不会听起来太蠢。

- Chaos

---

“NP在NP-完全问题中”的包含关系是错误的，正确的是“NP-完全问题在NP中”，因为NP-完全问题意味着“在NP中但不在P中（假设P≠NP）”。 - Thomash

@Thomash的评论一针见血。正如COME FROM所指出的那样，P、NP等仅适用于“问题”，而不是“解决问题的算法”。 - j_random_hacker

Answer 1

首先：

P在NP中；NP在NP-Complete中。因此，所有的P都可能在NP和NP-Complete中？

这是一个相当重要的声明，因为你所说的意味着 P=NP。目前还没有人能够证明或否定它。因此，事情的现状如下：

大多数人认为P≠NP。引用自Wikipedia：

在2002年的一次对100名研究者进行的调查中，有61位认为答案是否定的，9位认为是肯定的，22位不确定；8位认为这个问题可能与当前接受的公理无关，因此不可能证明或证伪。

一个简单的理解方式是：假设你已经得到了某个问题的解决方案。如果你能在多项式时间内验证解决方案是否正确，那么问题就是NP问题。显然，可以在多项式时间内解决的问题（P）都属于NP（你可以自己解决问题并在P时间内与正确答案比较）。

现在我们有几个问题可以在多项式时间内验证，但不能在相同的时间内解决。我们不确定是否永远不存在多项式时间解决方案，还是我们还没有想出来。

---

排序数字

• 给定一个数字列表，您可以在多项式时间内验证该列表是否已排序，因此该问题显然是 NP。

• 已知有算法可以在多项式时间内对数字列表进行排序（例如冒泡排序O（n ^ 2）等）。 因此，该问题是 P 。

希望这可以帮助您。

考虑阅读此博客。

- axiom

---

排序是对数字列表的排列，这表明它是一个非多项式时间暴力算法。因此，它可以属于 NP 类。 - human.js

@user1198898，它确实是NP问题，但不是你所列举的原因。 - axiom

那么，如果我告诉你，排序不能成为这些类中的任何一个部分呢？ - human.js

@user1198898 在这种情况下，我会推荐一些阅读材料，比如这个。 - axiom

是的，你展示的文件说排序作为一个决策问题是NP完全的。这意味着程序可以做出一个决策：是/否。上面提出的问题问的是排序是P还是NP，实际上这是未定义的，因为只有决策问题包括P和NP，而排序不属于其中任何一个！上面的问题可能需要重新表达一下。这就是我的意思。 - human.js

Answer 2

P、NP、NP-hard和NP-complete是问题的复杂度类；它们描述的是一个问题，而不是算法。

- COME FROM

---

好答案，棒极了的用户名 :) - j_random_hacker

要精确地说，决策问题。 - human.js

@human.js NP-hard 不仅限于决策问题。 - Rudolf Adamkovič