有些排序可以是P,NP和NP-Complete吗？

Question

我很困惑,经过一番阅读后,这是我的想法:

P在NP中,NP在NP完全中.因此,所有P都可以在NP和NP-Complete中？

这是否意味着存在可以是NP和NP-Complete的排序算法？

希望这听起来不是太愚蠢.

Answer 1

首先要做的事情:

P在NP中; NP是NP-Complete.因此,所有P都可以是NP和NP-Complete？

这是一个陈述,因为你所说的暗示P = NP.没有人能够证明这一点或其他方面.所以这是事态:

大多数人认为P!= NP.引自维基百科:

在2002年对100名研究人员的调查中,61人认为答案是否定的,9人认为答案是肯定的,22人不确定; 8认为这个问题可能与目前公认的公理无关,因此无法证明或反驳.

一个简单的理解方法是:假设您有一个问题的解决方案.如果您可以在多项式时间内验证解决方案是否正确,则问题是NP.显然,在多项式时间(P)中可以解决的每个问题都在NP中.现在我们有几个问题可以在多项式时间内验证,但不能在同一时间解决.我们不确定是否永远不会有多项式时间解决方案,或者我们还不能解决它.

排序数字

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

• 存在用于在多项式时间内对数字列表进行排序的已知算法.(冒泡排序O(n ^ 2)等).因此,问题是P.

希望这可以帮助.

考虑给这个博客读一读.

Answer 2

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